{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Title: #循环有序列表的插入"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Difficulty: #Medium"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Category Title: #Algorithms"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Tag Slug: #linked-list"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Name Translated: #链表"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution Name: insert"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Title: #循环有序列表的插入"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Content:\n",
    "<p>给定<strong>循环单调非递减列表</strong>中的一个点，写一个函数向这个列表中插入一个新元素&nbsp;<code>insertVal</code> ，使这个列表仍然是循环升序的。</p>\n",
    "\n",
    "<p>给定的可以是这个列表中任意一个顶点的指针，并不一定是这个列表中最小元素的指针。</p>\n",
    "\n",
    "<p>如果有多个满足条件的插入位置，可以选择任意一个位置插入新的值，插入后整个列表仍然保持有序。</p>\n",
    "\n",
    "<p>如果列表为空（给定的节点是 <code>null</code>），需要创建一个循环有序列表并返回这个节点。否则。请返回原先给定的节点。</p>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>示例 1：</strong></p>\n",
    "\n",
    "<p><img alt=\"\" src=\"https://assets.leetcode.com/uploads/2019/01/19/example_1_before_65p.jpg\" style=\"height: 149px; width: 250px;\" /><br />\n",
    "&nbsp;</p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>head = [3,4,1], insertVal = 2\n",
    "<strong>输出：</strong>[3,4,1,2]\n",
    "<strong>解释：</strong>在上图中，有一个包含三个元素的循环有序列表，你获得值为 3 的节点的指针，我们需要向表中插入元素 2 。新插入的节点应该在 1 和 3 之间，插入之后，整个列表如上图所示，最后返回节点 3 。\n",
    "\n",
    "<img alt=\"\" src=\"https://assets.leetcode.com/uploads/2019/01/19/example_1_after_65p.jpg\" style=\"height: 149px; width: 250px;\" />\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 2：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>head = [], insertVal = 1\n",
    "<strong>输出：</strong>[1]\n",
    "<strong>解释：</strong>列表为空（给定的节点是 <code>null</code>），创建一个循环有序列表并返回这个节点。\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 3：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>head = [1], insertVal = 0\n",
    "<strong>输出：</strong>[1,0]\n",
    "</pre>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>提示：</strong></p>\n",
    "\n",
    "<ul>\n",
    "\t<li><code>0 &lt;= Number of Nodes &lt;= 5 * 10^4</code></li>\n",
    "\t<li><code><font face=\"monospace\">-10^6 &lt;= Node.val &lt;= 10^6</font></code></li>\n",
    "\t<li><code>-10^6 &lt;=&nbsp;insertVal &lt;= 10^6</code></li>\n",
    "</ul>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><meta charset=\"UTF-8\" />注意：本题与主站 708&nbsp;题相同：&nbsp;<a href=\"https://leetcode-cn.com/problems/insert-into-a-sorted-circular-linked-list/\">https://leetcode-cn.com/problems/insert-into-a-sorted-circular-linked-list/</a></p>\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Description: [4ueAj6](https://leetcode.cn/problems/4ueAj6/description/)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solutions: [4ueAj6](https://leetcode.cn/problems/4ueAj6/solutions/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "test_cases = ['[3,4,1]\\n2', '[]\\n1', '[1]\\n0']"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def volunteerDeployment(self, finalCnt: List[int], totalNum: int, edges: List[List[int]], plans: List[List[int]]) -> List[int]:\n",
    "        finalCnt.insert(0,0)\n",
    "        n = len(finalCnt)\n",
    "        x = [0] * n\n",
    "        x[0] = 1\n",
    "        adj = [list() for i in range(n)]\n",
    "        for u,v in edges:\n",
    "            adj[u].append(v)\n",
    "            adj[v].append(u)\n",
    "        for num,idx in plans[::-1]:\n",
    "            if num == 1:\n",
    "                finalCnt[idx] *= 2\n",
    "                x[idx] *= 2\n",
    "            elif num == 2:\n",
    "                for v in adj[idx]:\n",
    "                    finalCnt[v] -= finalCnt[idx]\n",
    "                    x[v] -= x[idx]\n",
    "            else:\n",
    "                for v in adj[idx]:\n",
    "                    finalCnt[v] += finalCnt[idx]\n",
    "                    x[v] += x[idx]\n",
    "        zero_end = (totalNum - sum(finalCnt)) // sum(x)\n",
    "        for i in range(n):\n",
    "            finalCnt[i] += x[i] * zero_end\n",
    "        return finalCnt\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def relativeSortArray(self, arr1: List[int], arr2: List[int]) -> List[int]:\n",
    "        tnp = collections.Counter()\n",
    "        c = collections.Counter(arr1)\n",
    "        for k in list(c.keys()):\n",
    "            if k not in arr2:\n",
    "                tnp[k] = c[k]\n",
    "                del c[k]\n",
    "        for k,v in c.items():\n",
    "            if v!= 1:\n",
    "                while v-1:\n",
    "                    arr2.insert(arr2.index(k),k)\n",
    "                    v -= 1\n",
    "        print(tnp)\n",
    "        print(c)\n",
    "        tnp = sorted(tnp.items(), key=lambda d: d[0])\n",
    "        for k,v in dict(tnp).items():\n",
    "            while v:\n",
    "                arr2.append(k)\n",
    "                v -= 1\n",
    "        return arr2\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def largestRectangleArea(self, heights: List[int]) -> int:\n",
    "        # 从小到大排序, [h, s, e]\n",
    "        l = []\n",
    "        ret = 0\n",
    "\n",
    "        for i, h in enumerate(heights):\n",
    "            p = bisect.bisect_left(l, [h])\n",
    "            if p == len(l):\n",
    "                l.append([h, i, i + 1])\n",
    "                continue\n",
    "\n",
    "            if l[p][0] == h:\n",
    "                l[p][2] = i + 1\n",
    "                if p + 1 == len(l):\n",
    "                    continue\n",
    "            else:\n",
    "                l.insert(p, [h, i, i + 1])\n",
    "\n",
    "            # 修改p的起始坐标\n",
    "            l[p][1] = min(l[p][1], l[p + 1][1])\n",
    "\n",
    "            # 计算后面面积及删除\n",
    "            e = l[-1][-1]\n",
    "            for i in range(p + 1, len(l)):\n",
    "                ret = max(ret, l[i][0] * (e - l[i][1]))\n",
    "\n",
    "            del l[p + 1:]\n",
    "\n",
    "        # 计算面积\n",
    "        e = l[-1][-1]\n",
    "        for i in range(len(l)):\n",
    "            ret = max(ret, l[i][0] * (e - l[i][1]))\n",
    "\n",
    "        return ret\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def largestRectangleArea(self, heights: List[int]) -> int:\n",
    "        ans = 0\n",
    "        heights.append(0)\n",
    "        heights.insert(0, 0)\n",
    "        stack = []\n",
    "        stack.append(0)\n",
    "\n",
    "        for i in range(1, len(heights)):\n",
    "            if heights[i] > heights[stack[-1]]:\n",
    "                stack.append(i)\n",
    "            elif heights[i] == heights[stack[-1]]:\n",
    "                stack.pop()\n",
    "                stack.append(i)\n",
    "            else:\n",
    "                while len(stack) != 0 and heights[i] < heights[stack[-1]]:\n",
    "                    mid = stack.pop()\n",
    "                    if len(stack) != 0:\n",
    "                        left = stack[-1]\n",
    "                        right = i\n",
    "                        w = right - left - 1\n",
    "                        h = heights[mid]\n",
    "                        ans = max(ans, w * h)\n",
    "                stack.append(i)\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def largestRectangleArea(self, heights: List[int]) -> int:\n",
    "        stack = []\n",
    "        maxn = 0\n",
    "        length = len(heights)\n",
    "        \n",
    "        heights.append(0)\n",
    "        heights.insert(0, 0)\n",
    "        #print(heights)\n",
    "        for idx in range(length+2):\n",
    "            while stack and (heights[idx] < heights[stack[-1]]):\n",
    "                sum = (idx - stack[-2] - 1)*heights[stack[-1]]\n",
    "                #print(idx, stack[-2], stack[-1], sum)\n",
    "                if sum > maxn:\n",
    "                    maxn = sum\n",
    "                print(maxn)\n",
    "                stack.pop()\n",
    "\n",
    "            stack.append(idx)\n",
    "            #print(heights[idx])\n",
    "\n",
    "        return maxn"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def largestRectangleArea(self, heights: List[int]) -> int:\n",
    "        stack = []\n",
    "        heights.append(0)\n",
    "        heights.insert(0, 0)\n",
    "        n, ans = len(heights), 0\n",
    "\n",
    "        for i in range(n):\n",
    "            while stack and heights[i] < heights[stack[-1]]:\n",
    "                mid = stack.pop()\n",
    "                if stack:\n",
    "                    left = stack[-1]\n",
    "                    right = i\n",
    "                    w = right - left - 1\n",
    "                    h = heights[mid]\n",
    "                    ans = max(ans, w * h)\n",
    "            stack.append(i)\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def largestRectangleArea(self, heights: List[int]) -> int:\n",
    "        stack = []\n",
    "        heights.append(0)\n",
    "        heights.insert(0, 0)\n",
    "        n, ans = len(heights), 0\n",
    "\n",
    "        for i in range(n):\n",
    "            while stack and heights[i] < heights[stack[-1]]:\n",
    "                mid = stack.pop()\n",
    "                if stack:\n",
    "                    right = i\n",
    "                    left = stack[-1]\n",
    "                    w = right - left - 1\n",
    "                    h = heights[mid]\n",
    "                    ans = max(ans, w * h)\n",
    "\n",
    "            stack.append(i)\n",
    "        return ans\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def largestRectangleArea(self, heights: List[int]) -> int:\n",
    "        n = len(heights)\n",
    "        stack = []\n",
    "        left = []\n",
    "        for i in range(n):\n",
    "            while stack and heights[stack[-1]]>=heights[i]:\n",
    "                stack.pop()\n",
    "            if len(stack) == 0:\n",
    "                left.append(-1)\n",
    "            else:\n",
    "                left.append(stack[-1])\n",
    "            stack.append(i)\n",
    "        stack = []\n",
    "        right = []\n",
    "        for i in range(n-1,-1,-1):\n",
    "            while stack and heights[stack[-1]] >= heights[i]:\n",
    "                stack.pop()\n",
    "            if len(stack) == 0:\n",
    "                right.insert(0,n)\n",
    "            else:\n",
    "                right.insert(0,stack[-1])\n",
    "            stack.append(i)\n",
    "        res_list = [(right[i]-left[i]-1)*heights[i] for i in range(n)]\n",
    "        # print(left)\n",
    "        # print(right)\n",
    "        # print(res_list)\n",
    "        res = max(res_list)\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def find132pattern(self, nums: List[int]) -> bool:\n",
    "        # 对于每一个nums[j]，求其左边最小的数字nums[i] (i<j)，同时找其右边比自己小的最大数字nums[k] (k>j)\n",
    "        l_mins = [float('inf')]  # l_mins[i] = [0,i]中最小的数字\n",
    "        for j in range(1, len(nums)):\n",
    "            l_mins.append(min(l_mins[-1], nums[j - 1]))\n",
    "        sorted_arr = []\n",
    "        for j in range(len(nums) - 1, -1, -1):\n",
    "            idx = bisect.bisect_left(sorted_arr, nums[j])\n",
    "            if idx - 1 >= 0 and l_mins[j] < sorted_arr[idx - 1] < nums[j]:\n",
    "                return True\n",
    "            sorted_arr.insert(idx, nums[j])\n",
    "        return False\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    #运算符列表\n",
    "    operator=['+','-','*','/']\n",
    "\n",
    "    #运算顺序\n",
    "    # cal_strs=[]\n",
    "\n",
    "    def calculate(self,arr:list[int],k):\n",
    "        length=len(arr)\n",
    "\n",
    "        #只有一个数则判断其是否等于k\n",
    "        if length==1:\n",
    "            return abs(arr[0]-k)<1e-6\n",
    "        \n",
    "        #遍历所有可用操作符\n",
    "        for op in self.operator:\n",
    "            #遍历运算符前后的两个数的排列组合\n",
    "            for i in range(0,length):\n",
    "                start=0 if op in ('/','-') else i+1\n",
    "                for j in range(start,length):\n",
    "\n",
    "                    #约束条件 两个数不可相同 第一个操作数必须大于第二个操作数\n",
    "                    # if j==i or arr[i]<arr[j]:\n",
    "                    if j==i :\n",
    "                        continue\n",
    "            \n",
    "                    #约束条件 如果op为除号且不能整除 则抛弃\n",
    "                    # if op=='/' and (arr[j]==0 or arr[i]%arr[j]!=0):\n",
    "                    if op=='/' and (arr[j]==0):\n",
    "                        continue\n",
    "                    \n",
    "                    #计算该次计算的值\n",
    "                    if op=='+':\n",
    "                        num=arr[i]+arr[j]\n",
    "                    elif op=='-':\n",
    "                        num=arr[i]-arr[j]\n",
    "                    elif op=='*':\n",
    "                        num=arr[i]*arr[j]\n",
    "                    else:\n",
    "                        num=arr[i]/arr[j]\n",
    "                    # num=eval(f\"{arr[i]}{op}{arr[j]}\")\n",
    "                    \n",
    "                    #生成新的数组 除去第i j个元素 加上num\n",
    "                    new_arr=[]\n",
    "                    for index,n in enumerate(arr):\n",
    "                        if index!=i and index!=j:\n",
    "                            new_arr.append(n)\n",
    "                    new_arr.append(num)\n",
    "        \n",
    "                    #使用新数组计算24点 如成功则返回成功\n",
    "                    if self.calculate(new_arr,k):\n",
    "                        # cal_strs.insert(0,f\"{arr[i]}{op}{arr[j]}={num}\")\n",
    "                        return True\n",
    "                \n",
    "        return False\n",
    "\n",
    "\n",
    "    def judgePoint24(self, cards: List[int]) -> bool:\n",
    "        \"\"\"\n",
    "        :type cards: List[int]\n",
    "        :rtype: bool\n",
    "        \"\"\"\n",
    "        return self.calculate(cards,24)\n",
    "    "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    #运算符列表\n",
    "    operator=['+','-','*','/']\n",
    "\n",
    "    #运算顺序\n",
    "    # cal_strs=[]\n",
    "\n",
    "    def calculate(self,arr:list[int],k):\n",
    "        length=len(arr)\n",
    "\n",
    "        #只有一个数则判断其是否等于k\n",
    "        if length==1:\n",
    "            return abs(arr[0]-k)<1e-6\n",
    "        \n",
    "        #遍历所有可用操作符\n",
    "        for op in self.operator:\n",
    "            #遍历运算符前后的两个数的排列组合\n",
    "            for i in range(0,length):\n",
    "                start=0 if op in ('/','-') else i+1\n",
    "                for j in range(start,length):\n",
    "\n",
    "                    #约束条件 两个数不可相同 第一个操作数必须大于第二个操作数\n",
    "                    # if j==i or arr[i]<arr[j]:\n",
    "                    if j==i :\n",
    "                        continue\n",
    "            \n",
    "                    #约束条件 如果op为除号且不能整除 则抛弃\n",
    "                    # if op=='/' and (arr[j]==0 or arr[i]%arr[j]!=0):\n",
    "                    if op=='/' and (arr[j]==0):\n",
    "                        continue\n",
    "                    \n",
    "                    #计算该次计算的值\n",
    "                    if op=='+':\n",
    "                        num=arr[i]+arr[j]\n",
    "                    elif op=='-':\n",
    "                        num=arr[i]-arr[j]\n",
    "                    elif op=='*':\n",
    "                        num=arr[i]*arr[j]\n",
    "                    else:\n",
    "                        num=arr[i]/arr[j]\n",
    "                    # num=eval(f\"{arr[i]}{op}{arr[j]}\")\n",
    "                    \n",
    "                    #生成新的数组 除去第i j个元素 加上num\n",
    "                    new_arr=[]\n",
    "                    for index,n in enumerate(arr):\n",
    "                        if index!=i and index!=j:\n",
    "                            new_arr.append(n)\n",
    "                    new_arr.append(num)\n",
    "        \n",
    "                    #使用新数组计算24点 如成功则返回成功\n",
    "                    if self.calculate(new_arr,k):\n",
    "                        # cal_strs.insert(0,f\"{arr[i]}{op}{arr[j]}={num}\")\n",
    "                        return True\n",
    "                \n",
    "        return False\n",
    "\n",
    "\n",
    "    def judgePoint24(self, cards: List[int]) -> bool:\n",
    "        \"\"\"\n",
    "        :type cards: List[int]\n",
    "        :rtype: bool\n",
    "        \"\"\"\n",
    "        return self.calculate(cards,24)\n",
    "    "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    #运算符列表\n",
    "    operator=['+','-','*','/']\n",
    "\n",
    "    #运算顺序\n",
    "    # cal_strs=[]\n",
    "\n",
    "    def calculate(self,arr:list[int],k):\n",
    "        length=len(arr)\n",
    "\n",
    "        #只有一个数则判断其是否等于k\n",
    "        if length==1:\n",
    "            return abs(arr[0]-k)<1e-6\n",
    "        \n",
    "        #遍历所有可用操作符\n",
    "        for op in self.operator:\n",
    "            #遍历运算符前后的两个数的排列组合\n",
    "            for i in range(0,length):\n",
    "                for j in range(0,length):\n",
    "\n",
    "                    #约束条件 两个数不可相同 第一个操作数必须大于第二个操作数\n",
    "                    # if j==i or arr[i]<arr[j]:\n",
    "                    if j==i :\n",
    "                        continue\n",
    "            \n",
    "                    #约束条件 如果op为除号且不能整除 则抛弃\n",
    "                    # if op=='/' and (arr[j]==0 or arr[i]%arr[j]!=0):\n",
    "                    if op=='/' and (arr[j]==0):\n",
    "                        continue\n",
    "                    \n",
    "                    #计算该次计算的值\n",
    "                    num=eval(f\"{arr[i]}{op}{arr[j]}\")\n",
    "                    \n",
    "                    #生成新的数组 除去第i j个元素 加上num\n",
    "                    new_arr=[]\n",
    "                    for index,n in enumerate(arr):\n",
    "                        if index!=i and index!=j:\n",
    "                            new_arr.append(n)\n",
    "                    new_arr.append(num)\n",
    "        \n",
    "                    #使用新数组计算24点 如成功则返回成功\n",
    "                    if self.calculate(new_arr,k):\n",
    "                        # cal_strs.insert(0,f\"{arr[i]}{op}{arr[j]}={num}\")\n",
    "                        return True\n",
    "                \n",
    "        return False\n",
    "\n",
    "\n",
    "    def judgePoint24(self, cards: List[int]) -> bool:\n",
    "        \"\"\"\n",
    "        :type cards: List[int]\n",
    "        :rtype: bool\n",
    "        \"\"\"\n",
    "        return self.calculate(cards,24)\n",
    "    "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def judgePoint24(self, cards: List[int]) -> bool:\n",
    "        TARGET = 24\n",
    "        EPSLION = 1e-6\n",
    "        ADD, MULIPLY, SUBTRACT, DIVIDE = 0,1,2,3\n",
    "\n",
    "        def dfs(nums:List[int])->bool:\n",
    "            if not nums:\n",
    "                return False\n",
    "            if len(nums)==1:\n",
    "                return abs(TARGET - nums[0])<EPSLION\n",
    "            \n",
    "            for i,x in enumerate(nums):\n",
    "                for j,y in enumerate(nums):\n",
    "                    if i!=j:\n",
    "                        newNums = []\n",
    "                        for k,z in enumerate(nums):\n",
    "                            if k!=i and k!=j:\n",
    "                                newNums.append(z)\n",
    "                        for k in range(4):\n",
    "                            if k<2 and i>j:\n",
    "                                continue\n",
    "                            if k==ADD:\n",
    "                                newNums.insert(0, x+y)\n",
    "                            elif k == MULIPLY:\n",
    "                                newNums.insert(0, x*y)\n",
    "                            elif k==SUBTRACT:\n",
    "                                newNums.insert(0, x-y)\n",
    "                            elif k==DIVIDE:\n",
    "                                if abs(y)<EPSLION:\n",
    "                                    continue\n",
    "                                newNums.insert(0, x/y)\n",
    "                            if dfs(newNums):\n",
    "                                return True\n",
    "                            newNums.pop(0)\n",
    "            return False\n",
    "        return dfs(cards)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\n",
    "from fractions import Fraction\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def __init__(self):\n",
    "        self.can = False\n",
    "\n",
    "    def judgePoint24(self, cards: list) -> bool:\n",
    "        cp = list(cards)\n",
    "        self.dfs(cp)\n",
    "\n",
    "        return self.can\n",
    "\n",
    "    def dfs(self, cards):\n",
    "        if len(cards) == 1:\n",
    "            # print(cards[0])\n",
    "            if abs(cards[0] - 24.0) < 1e-6:\n",
    "                print(cards)\n",
    "                self.can = True\n",
    "            return\n",
    "\n",
    "        for i in range(len(cards)):\n",
    "            for j in range(i + 1, len(cards)):\n",
    "                x, y = Fraction(cards[i]), Fraction(cards[j])\n",
    "                cards.pop(j)\n",
    "                for op in ['+', '-', '*', '/']:\n",
    "                    for seq in [1, 0]:\n",
    "                        if op in ['+', '-', '*']:\n",
    "                            res = eval(str(x) + op + str(y)) if seq else eval(str(y) + op + str(x))\n",
    "                        else:\n",
    "                            if seq:\n",
    "                                if y == 0:\n",
    "                                    continue\n",
    "                                res = Fraction(x, y)\n",
    "                            else:\n",
    "                                if x == 0:\n",
    "                                    continue\n",
    "                                res = Fraction(y,x)\n",
    "\n",
    "                        cards[i] = res\n",
    "                        self.dfs(cards)\n",
    "                cards[i] = x\n",
    "                cards.insert(j, y)\n",
    "                \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def czh(self,i,result,path,cards,booll):\n",
    "        a={0:[0,4],1:[0,6],2:[2,6],3:[2,8],4:[4,8]}\n",
    "        b={0:\"+\",1:\"-\",2:\"*\",3:\"/\"}\n",
    "        if booll:\n",
    "            return\n",
    "        if i==4:\n",
    "            for kk in range(0,5):\n",
    "                s=path[:]\n",
    "                s.insert(a[kk][0],\"(\")\n",
    "                s.insert(a[kk][1],\")\")\n",
    "                ss = ''.join([str(num) for num in s])\n",
    "                try:\n",
    "                    rr=eval(ss)\n",
    "                except:\n",
    "                    aaa=1\n",
    "                \n",
    "                if abs(rr-24)<0.001:\n",
    "                    result.append(s[:])\n",
    "                    booll=True\n",
    "            s = path[:]\n",
    "            s.insert(0, \"(\")\n",
    "            s.insert(4, \")\")\n",
    "            s.insert(6, \"(\")\n",
    "            s.insert(10, \")\")\n",
    "            ss = ''.join([str(num) for num in s])\n",
    "            try:\n",
    "                rr = eval(ss)\n",
    "            except:\n",
    "                aaa = 1\n",
    "            if abs(rr - 24) < 0.001:\n",
    "                result.append(s[:])\n",
    "\n",
    "            return\n",
    "        for kk in range (0,4):\n",
    "            path.append(b[kk])\n",
    "            path.append(cards[i])\n",
    "            self.czh(i+1,result,path,cards,booll)\n",
    "            path.pop()\n",
    "            path.pop()\n",
    "        return\n",
    "    def simba(self,i,cards,pathh,rresult):\n",
    "        if i==4:\n",
    "            p=[]\n",
    "            for kkk in pathh:\n",
    "                p.append(cards[kkk])\n",
    "            rresult.append(p)\n",
    "            return\n",
    "        for j in range (0,4):\n",
    "            if not(j in pathh):\n",
    "                pathh.append(j)\n",
    "                self.simba(i+1,cards,pathh,rresult)\n",
    "                pathh.pop() \n",
    "    def judgePoint24(self, cards: List[int]) -> bool:\n",
    "       result=[]\n",
    "\n",
    "       rresult=[]\n",
    "       self.simba(0,cards,[],rresult)\n",
    "       for i in rresult:\n",
    "           path=[]\n",
    "           path.append(i[0])\n",
    "           self.czh(1,result,path,i,False)\n",
    "           if len(result)>0:\n",
    "               break\n",
    "       if len(result)>0:\n",
    "           return(True)\n",
    "       else:\n",
    "           return(False)\n",
    "        \n",
    "    \n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minSubArrayLen(self, target: int, nums: List[int]) -> int:\n",
    "        '''\n",
    "        l = 0                           # 初始化左边界\n",
    "        n = len(nums)\n",
    "        out = n+1                       # 初始化返回值 out = 最小值 or 最大值\n",
    "        res = 0\n",
    "        for r in range(n):              # for 右边界 in 可迭代对象:\n",
    "            res += nums[r]                  # 更新窗口内部信息\n",
    "            while res >= target:            # while 根据题意进行调整：\n",
    "                out = min(out, r-l+1)           # 比较并更新out(收缩场景时)\n",
    "                res -= nums[l]\n",
    "                l += 1                          # 扩张或收缩窗口大小\n",
    "                                            # 比较并更新out(扩张场景时)，本题为收缩场景\n",
    "        return 0 if out == n+1 else out\n",
    "        '''\n",
    "        n = len(nums)\n",
    "        part_sum = []\n",
    "        for i in range(n):\n",
    "            part_sum.append(sum(nums[:i+1]))\n",
    "        part_sum.insert(0,0)\n",
    "        print(part_sum)\n",
    "        \n",
    "        if part_sum[-1] < target:\n",
    "            return 0\n",
    "        \n",
    "        l = 0\n",
    "        out = n+1\n",
    "        for i in range(n+1):\n",
    "            new_target = part_sum[i] + target\n",
    "            l = i+1\n",
    "            r = n\n",
    "            while l < r:\n",
    "                mid = (l+r) // 2\n",
    "                if part_sum[mid] < new_target:\n",
    "                    l = mid + 1\n",
    "                else:\n",
    "                    r = mid\n",
    "            if part_sum[r] >= new_target:\n",
    "                out = min(out, r-i)\n",
    "            print(new_target,r,i,r-i)\n",
    "        return out\n",
    "            \n",
    "\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\"\"\"\n",
    "# Definition for a Node.\n",
    "class Node:\n",
    "    def __init__(self, val=None, next=None):\n",
    "        self.val = val\n",
    "        self.next = next\n",
    "\"\"\"\n",
    "\n",
    "class Solution:\n",
    "    def insert(self, head: 'Node', insertVal: int) -> 'Node':\n",
    "        node = Node(insertVal)\n",
    "        if head is None:\n",
    "            node.next = node\n",
    "            return node\n",
    "        elif head.next == head:\n",
    "            head.next = node\n",
    "            node.next = head\n",
    "            return head\n",
    "\n",
    "        prev, cur = head, head.next\n",
    "        while cur != head:\n",
    "            if prev.val <= insertVal <= cur.val:\n",
    "                break\n",
    "            if prev.val > cur.val:\n",
    "                if insertVal > prev.val or insertVal < cur.val:\n",
    "                    break\n",
    "            prev, cur = cur, cur.next\n",
    "        prev.next = node\n",
    "        node.next = cur\n",
    "        return head"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\"\"\"\n",
    "# Definition for a Node.\n",
    "class Node:\n",
    "    def __init__(self, val=None, next=None):\n",
    "        self.val = val\n",
    "        self.next = next\n",
    "\"\"\"\n",
    "\n",
    "class Solution:\n",
    "    def insert(self, head: 'Node', insertVal: int) -> 'Node':\n",
    "        if not head:\n",
    "            newNode = Node(insertVal)\n",
    "            newNode.next = newNode\n",
    "            return newNode\n",
    "        if  head.next == head:\n",
    "            head.next = Node(insertVal, head)\n",
    "            return head\n",
    "        \n",
    "        pre = head\n",
    "        cur = head.next\n",
    "        while cur != head:\n",
    "            if pre.val <= insertVal and cur.val >= insertVal:\n",
    "                pre.next = Node(insertVal, cur)\n",
    "                break\n",
    "            elif pre.val > cur.val and (insertVal <= cur.val or insertVal >= pre.val):\n",
    "                pre.next = Node(insertVal, cur)\n",
    "                break\n",
    "            else:\n",
    "                pre = cur\n",
    "                cur = cur.next\n",
    "\n",
    "        if cur == head:\n",
    "            pre.next = Node(insertVal, cur)\n",
    "        return head\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\"\"\"\n",
    "# Definition for a Node.\n",
    "class Node:\n",
    "    def __init__(self, val=None, next=None):\n",
    "        self.val = val\n",
    "        self.next = next\n",
    "\"\"\"\n",
    "\n",
    "class Solution:\n",
    "    def insert(self, head: 'Node', insertVal: int) -> 'Node':\n",
    "        node = Node(insertVal)\n",
    "        if head is None:\n",
    "           node.next = node\n",
    "           return node\n",
    "        if head.next == head:\n",
    "            head.next = node\n",
    "            node.next = head\n",
    "            return head\n",
    "        curr = head\n",
    "        next = head.next\n",
    "        while next != head:\n",
    "            if curr.val <= insertVal <= next.val:\n",
    "                break\n",
    "            if curr.val > next.val:\n",
    "                if insertVal >curr.val or insertVal < next.val:\n",
    "                    break\n",
    "            curr = curr.next\n",
    "            next = next.next\n",
    "        curr.next = node\n",
    "        node.next = next\n",
    "        return head\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\"\"\"\n",
    "# Definition for a Node.\n",
    "class Node:\n",
    "    def __init__(self, val=None, next=None):\n",
    "        self.val = val\n",
    "        self.next = next\n",
    "\"\"\"\n",
    "\n",
    "class Solution:\n",
    "    def insert(self, head: 'Node', insertVal: int) -> 'Node':\n",
    "        node = Node(insertVal)\n",
    "\n",
    "        if head is None:\n",
    "            node.next = node\n",
    "            return node\n",
    "        \n",
    "        if head.next == head:\n",
    "            head.next = node\n",
    "            node.next = head\n",
    "            return head\n",
    "        \n",
    "        curr = head\n",
    "        nextNode = head.next\n",
    "\n",
    "        while nextNode != head:\n",
    "            if curr.val <= insertVal <= nextNode.val:\n",
    "                break\n",
    "            if curr.val > nextNode.val:\n",
    "                if insertVal > curr.val or insertVal < nextNode.val:\n",
    "                    break\n",
    "            curr = curr.next\n",
    "            nextNode = nextNode.next\n",
    "        curr.next = node\n",
    "        node.next = nextNode\n",
    "        return head\n",
    "\n",
    "\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\"\"\"\n",
    "# Definition for a Node.\n",
    "class Node:\n",
    "    def __init__(self, val=None, next=None):\n",
    "        self.val = val\n",
    "        self.next = next\n",
    "\"\"\"\n",
    "\n",
    "class Solution:\n",
    "    def insert(self, head: 'Node', insertVal: int) -> 'Node':\n",
    "        if head == None:\n",
    "            head = Node(insertVal,None)\n",
    "            head.next = head\n",
    "            return head\n",
    "        elif head == head.next:\n",
    "            nextnode = head.next\n",
    "            head.next = Node(insertVal,nextnode)\n",
    "            return head     \n",
    "        else:\n",
    "            tmp = head\n",
    "            while True:\n",
    "                if tmp.val<=tmp.next.val and tmp.val<=insertVal<=tmp.next.val:\n",
    "                    nextnode = tmp.next\n",
    "                    tmp.next = Node(insertVal,nextnode)\n",
    "                    break\n",
    "                elif tmp.val>tmp.next.val and (tmp.val<=insertVal or insertVal<=tmp.next.val):\n",
    "                    nextnode = tmp.next\n",
    "                    tmp.next = Node(insertVal,nextnode)\n",
    "                    break\n",
    "                elif tmp.val==tmp.next.val and tmp.next==head:\n",
    "                    nextnode = tmp.next\n",
    "                    tmp.next = Node(insertVal,nextnode)\n",
    "                    break\n",
    "                tmp = tmp.next\n",
    "            return head\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\"\"\"\n",
    "# Definition for a Node.\n",
    "class Node:\n",
    "    def __init__(self, val=None, next=None):\n",
    "        self.val = val\n",
    "        self.next = next\n",
    "\"\"\"\n",
    "\n",
    "class Solution:\n",
    "    def insert(self, head: 'Node', insertVal: int) -> 'Node':\n",
    "        node = Node(insertVal)\n",
    "        if not head:\n",
    "            head = node\n",
    "            head.next = head\n",
    "            return head\n",
    "        \n",
    "        if head.next == head:\n",
    "            head.next = node\n",
    "            node.next = head\n",
    "            return head\n",
    "        \n",
    "        cur = head\n",
    "        nxt = cur.next\n",
    "        while nxt != head:\n",
    "            if cur.val <= insertVal <= nxt.val:\n",
    "                break\n",
    "            if cur.val > nxt.val:\n",
    "                if insertVal > cur.val or insertVal < nxt.val:\n",
    "                    break\n",
    "            cur = nxt\n",
    "            nxt = nxt.next\n",
    "        \n",
    "        cur.next = node\n",
    "        node.next = nxt\n",
    "        return head\n",
    "\n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\"\"\"\n",
    "# Definition for a Node.\n",
    "class Node:\n",
    "    def __init__(self, val=None, next=None):\n",
    "        self.val = val\n",
    "        self.next = next\n",
    "\"\"\"\n",
    "\n",
    "class Solution:\n",
    "    def insert(self, head: 'Node', insertVal: int) -> 'Node':\n",
    "        if not head:\n",
    "            node = Node(insertVal)\n",
    "            node.next = node\n",
    "            return node\n",
    "        cur = head\n",
    "        while cur.next != head:\n",
    "            if cur.val <= insertVal <= cur.next.val:\n",
    "                break\n",
    "            if cur.val > cur.next.val and (insertVal < cur.next.val or insertVal > cur.val):\n",
    "                    break\n",
    "            cur = cur.next\n",
    "        cur.next = Node(insertVal,cur.next)\n",
    "        return head"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\"\"\"\n",
    "# Definition for a Node.\n",
    "class Node:\n",
    "    def __init__(self, val=None, next=None):\n",
    "        self.val = val\n",
    "        self.next = next\n",
    "\"\"\"\n",
    "\n",
    "class Solution:\n",
    "    def insert(self, head: 'Node', insertVal: int) -> 'Node':\n",
    "        if head is None:\n",
    "            head = Node(insertVal, None)\n",
    "            head.next = head\n",
    "            return head\n",
    "\n",
    "        p = head\n",
    "        while p.next != head:\n",
    "            if (insertVal >= p.val and insertVal <= p.next.val) or (p.next.val < p.val and (insertVal < p.next.val or insertVal > p.val)):\n",
    "                break\n",
    "            p = p.next\n",
    "\n",
    "        p.next = Node(insertVal, p.next)\n",
    "        return head\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\"\"\"\n",
    "# Definition for a Node.\n",
    "class Node:\n",
    "    def __init__(self, val=None, next=None):\n",
    "        self.val = val\n",
    "        self.next = next\n",
    "\"\"\"\n",
    "\n",
    "class Solution:\n",
    "    def insert(self, head: 'Node', insertVal: int) -> 'Node':\n",
    "        if not head:\n",
    "            head = Node(val=insertVal)\n",
    "            head.next = head\n",
    "            return head\n",
    "        if not head.next:\n",
    "            head.next = Node(val=insertVal)\n",
    "            return head\n",
    "        cur = head\n",
    "        while True:\n",
    "            if (cur.val <= insertVal and insertVal<=cur.next.val) or (cur.val <= insertVal and cur.next.val < cur.val) or (cur.next.val >= insertVal and cur.next.val < cur.val) or cur.next == head:\n",
    "                tmp = cur.next\n",
    "                add = Node(val=insertVal)\n",
    "                cur.next = add\n",
    "                add.next = tmp\n",
    "                break\n",
    "            cur = cur.next\n",
    "        return head        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\"\"\"\n",
    "# Definition for a Node.\n",
    "class Node:\n",
    "    def __init__(self, val=None, next=None):\n",
    "        self.val = val\n",
    "        self.next = next\n",
    "\"\"\"\n",
    "\n",
    "class Solution:\n",
    "    def insert(self, head: 'Node', insertVal: int) -> 'Node':\n",
    "        if head == None :\n",
    "             head = Node(val=insertVal)\n",
    "             head.next = head \n",
    "             return head\n",
    "        p = head\n",
    "        while p.next !=head:\n",
    "            if insertVal >= p.val and  insertVal <= p.next.val:\n",
    "                break\n",
    "            if insertVal <=p.val and  p.val<=insertVal<=p.next.val:\n",
    "                break\n",
    "            if p.val > p.next.val and p.val <= insertVal:\n",
    "                break\n",
    "            if p.val>p.next.val and p.next.val >=insertVal:\n",
    "                break\n",
    "            p = p.next\n",
    "\n",
    "         \n",
    "        a = Node(insertVal)\n",
    "        a.next = p.next\n",
    "        p.next = a\n",
    "        return head"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\"\"\"\n",
    "# Definition for a Node.\n",
    "class Node:\n",
    "    def __init__(self, val=None, next=None):\n",
    "        self.val = val\n",
    "        self.next = next\n",
    "\"\"\"\n",
    "\n",
    "class Solution:\n",
    "    def insert(self, head: 'Node', insertVal: int) -> 'Node':\n",
    "        newNode = Node(insertVal)\n",
    "        if head is None:\n",
    "            newNode.next = newNode\n",
    "            return newNode\n",
    "        cur, nxt = head, head.next\n",
    "        if cur == nxt:\n",
    "            cur.next = newNode\n",
    "            newNode.next = nxt\n",
    "            return head\n",
    "        while nxt != head:\n",
    "            if cur.val <= insertVal <= nxt.val:\n",
    "                break\n",
    "            if cur.val > nxt.val:\n",
    "                if insertVal > cur.val or insertVal < nxt.val:\n",
    "                    break\n",
    "            cur, nxt = nxt, nxt.next\n",
    "        # 如果因为nxt == head走出循环，那么此时将节点插入一定没错\n",
    "        cur.next = newNode\n",
    "        newNode.next = nxt\n",
    "        return head\n",
    "        \n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\"\"\"\n",
    "# Definition for a Node.\n",
    "class Node:\n",
    "    def __init__(self, val=None, next=None):\n",
    "        self.val = val\n",
    "        self.next = next\n",
    "\"\"\"\n",
    "\n",
    "class Solution:\n",
    "    def insert(self, head: 'Node', insertVal: int) -> 'Node':\n",
    "        tmp = Node(insertVal)\n",
    "        if not head:\n",
    "            tmp.next=tmp\n",
    "            return tmp\n",
    "        buff=[]\n",
    "        dummy=Node()\n",
    "        dummy2=Node()\n",
    "        dummy.next=head\n",
    "        while True:\n",
    "            val,next_val=head.val, head.next.val\n",
    "            if head.next==dummy.next:\n",
    "                head=dummy.next\n",
    "                break\n",
    "            head=head.next\n",
    "            if val>next_val:\n",
    "                break\n",
    "        dummy2.next=head\n",
    "        buff.append([head, head.next])\n",
    "        head=head.next\n",
    "        while dummy2.next!=head:\n",
    "            buff.append([head,head.next])\n",
    "            head=head.next\n",
    "        buff[-1][1]=dummy2.next\n",
    "        inserted=False\n",
    "        for i in range(len(buff)):\n",
    "            [node, next_node] = buff[i]\n",
    "            if node.val<=insertVal<=next_node.val:\n",
    "                node.next, tmp.next=tmp, next_node\n",
    "                inserted=True\n",
    "                break\n",
    "        if not inserted:\n",
    "            [node, next_node] = buff[-1]\n",
    "            node.next, tmp.next=tmp, next_node\n",
    "        return dummy.next\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\"\"\"\n",
    "# Definition for a Node.\n",
    "class Node:\n",
    "    def __init__(self, val=None, next=None):\n",
    "        self.val = val\n",
    "        self.next = next\n",
    "\"\"\"\n",
    "\n",
    "class Solution:\n",
    "    def insert(self, head: 'Node', insertVal: int) -> 'Node':\n",
    "        cur = head\n",
    "        if not head:\n",
    "            tmp=Node(insertVal)\n",
    "            tmp.next = tmp\n",
    "            return tmp\n",
    "        if not head.next:\n",
    "            tmp=Node(insertVal)\n",
    "            tmp.next = head\n",
    "            head.next = tmp\n",
    "            return head\n",
    "        flag = 0\n",
    "        minNode = head\n",
    "        maxNode = head\n",
    "        time =0\n",
    "        while cur:\n",
    "            if(cur.val<minNode.val):\n",
    "                minNode=cur\n",
    "            if cur.val>=maxNode.val:\n",
    "                maxNode=cur\n",
    "            if cur.next and cur.next==head:\n",
    "                break\n",
    "            cur = cur.next\n",
    "        \n",
    "        cur =minNode\n",
    "        ans = None\n",
    "        while cur:\n",
    "            tmp = cur.next\n",
    "            \n",
    "            if tmp and(cur.val<insertVal and tmp.val>=insertVal):\n",
    "                flag=1\n",
    "                node = Node(insertVal)\n",
    "                cur.next = node\n",
    "                node.next = tmp\n",
    "                break\n",
    "            if tmp==minNode:\n",
    "                break\n",
    "            if tmp.next and tmp.next==minNode:\n",
    "                ans=tmp\n",
    "            cur = cur.next\n",
    "        # return minNode\n",
    "        if ans==None:\n",
    "            ans=head\n",
    "        if flag==0:\n",
    "            cur = head\n",
    "            while cur:\n",
    "                if(cur.val==maxNode.val and cur.next.val==minNode.val):\n",
    "                    node =Node(insertVal)\n",
    "                    node.next=cur.next\n",
    "                    cur.next=node\n",
    "                    break \n",
    "                cur=cur.next\n",
    "\n",
    "        return head\n",
    "        \n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def insert(self, head: 'Node', insertVal: int) -> 'Node':\n",
    "        node = Node(insertVal)\n",
    "        if head is None:\n",
    "            node.next = node\n",
    "            return node\n",
    "        if head.next == head:\n",
    "            head.next = node\n",
    "            node.next = head\n",
    "            return head\n",
    "        curr = head\n",
    "        next = head.next\n",
    "        while next != head:\n",
    "            if curr.val <= insertVal <= next.val:\n",
    "                break\n",
    "            if curr.val > next.val:\n",
    "                if insertVal > curr.val or insertVal < next.val:\n",
    "                    break\n",
    "            curr = curr.next\n",
    "            next = next.next\n",
    "        curr.next = node\n",
    "        node.next = next\n",
    "        return head"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\"\"\"\n",
    "# Definition for a Node.\n",
    "class Node:\n",
    "    def __init__(self, val=None, next=None):\n",
    "        self.val = val\n",
    "        self.next = next\n",
    "\"\"\"\n",
    "\n",
    "class Solution:\n",
    "    def insert(self, head: 'Node', insertVal: int) -> 'Node':\n",
    "        newnode = Node(insertVal)\n",
    "        if not head: \n",
    "            newnode.next = newnode\n",
    "            return newnode\n",
    "        if head.next == head: \n",
    "            head.next = newnode\n",
    "            newnode.next = head\n",
    "            return head\n",
    "        cur, pre = head.next, head\n",
    "\n",
    "        while cur != head:\n",
    "            if insertVal >= pre.val and insertVal <= cur.val:\n",
    "                break\n",
    "            if cur.val < pre.val:\n",
    "                if insertVal < cur.val or insertVal > pre.val:\n",
    "                    break\n",
    "            pre = cur\n",
    "            cur = cur.next\n",
    "        pre.next = newnode\n",
    "        newnode.next = cur\n",
    "        return head\n",
    "\n",
    "            \n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\"\"\"\n",
    "# Definition for a Node.\n",
    "class Node:\n",
    "    def __init__(self, val=None, next=None):\n",
    "        self.val = val\n",
    "        self.next = next\n",
    "\"\"\"\n",
    "\n",
    "class Solution:\n",
    "    def insert(self, head: 'Node', insertVal: int) -> 'Node':\n",
    "        node = Node(insertVal)\n",
    "        if head is None:\n",
    "            node.next = node\n",
    "            return node\n",
    "        if head.next == head:\n",
    "            head.next = node\n",
    "            node.next = head\n",
    "            return head\n",
    "        curr = head\n",
    "        next = head.next\n",
    "        while next != head:\n",
    "            if curr.val <= insertVal <= next.val:\n",
    "                break\n",
    "            if curr.val > next.val:\n",
    "                if insertVal > curr.val or insertVal < next.val:\n",
    "                    break\n",
    "            curr = curr.next\n",
    "            next = next.next\n",
    "        curr.next = node\n",
    "        node.next = next\n",
    "        return head\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\"\"\"\n",
    "# Definition for a Node.\n",
    "class Node:\n",
    "    def __init__(self, val=None, next=None):\n",
    "        self.val = val\n",
    "        self.next = next\n",
    "\"\"\"\n",
    "\n",
    "class Solution:\n",
    "    def insert(self, head: 'Node', insertVal: int) -> 'Node':\n",
    "        if head == None:\n",
    "            head = Node(insertVal)\n",
    "            head.next = head\n",
    "            return head\n",
    "        elif head.next == head:\n",
    "            NNode = Node(insertVal)\n",
    "            head.next = NNode\n",
    "            NNode.next = head\n",
    "            return head\n",
    "        else:\n",
    "            min_val = head.val\n",
    "            max_val = head.val\n",
    "            curr = head.next\n",
    "            while curr != head:\n",
    "                if curr.val < min_val:\n",
    "                    min_val = curr.val\n",
    "                if curr.val > max_val:\n",
    "                    max_val = curr.val\n",
    "                curr = curr.next\n",
    "            \n",
    "            NEXT = curr.next\n",
    "            while True:\n",
    "                if curr.val == max_val and NEXT.val == min_val:\n",
    "                    break\n",
    "                curr = NEXT\n",
    "                NEXT = NEXT.next\n",
    "\n",
    "            if insertVal <= NEXT.val or insertVal >= curr.val:\n",
    "                NNode = Node(insertVal)\n",
    "                curr.next = NNode\n",
    "                NNode.next = NEXT\n",
    "                return head\n",
    "            else:\n",
    "                curr = NEXT\n",
    "                NEXT = NEXT.next\n",
    "                while True:\n",
    "                    if curr.val <= insertVal and NEXT.val >= insertVal:\n",
    "                        NNode = Node(insertVal)\n",
    "                        curr.next = NNode\n",
    "                        NNode.next = NEXT\n",
    "                        return head\n",
    "                    else:\n",
    "                        curr = NEXT\n",
    "                        NEXT = NEXT.next"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\"\"\"\n",
    "# Definition for a Node.\n",
    "class Node:\n",
    "    def __init__(self, val=None, next=None):\n",
    "        self.val = val\n",
    "        self.next = next\n",
    "\"\"\"\n",
    "\n",
    "class Solution:\n",
    "    def insert(self, head: 'Node', insertVal: int) -> 'Node':\n",
    "        node = Node(insertVal)\n",
    "        # 原来的链表中无元素\n",
    "        if head is None:\n",
    "            node.next = node\n",
    "            return node\n",
    "        # 原来的链表中只有一个元素\n",
    "        if head.next == head:\n",
    "            head.next = node\n",
    "            node.next = head\n",
    "            return head\n",
    "        curr = head\n",
    "        next = head.next\n",
    "        while next != head:\n",
    "            if curr.val <= insertVal <= next.val:\n",
    "                break\n",
    "            if curr.val > next.val:\n",
    "                if insertVal > curr.val or insertVal < next.val:\n",
    "                    break\n",
    "            curr = curr.next\n",
    "            next = next.next\n",
    "        curr.next = node\n",
    "        node.next = next\n",
    "        return head"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\"\"\"\n",
    "# Definition for a Node.\n",
    "class Node:\n",
    "    def __init__(self, val=None, next=None):\n",
    "        self.val = val\n",
    "        self.next = next\n",
    "\"\"\"\n",
    "\n",
    "class Solution:\n",
    "    def insert(self, head: 'Node', insertVal: int) -> 'Node':\n",
    "        node = Node(insertVal)\n",
    "        if not head:\n",
    "            node.next = node \n",
    "            return node \n",
    "        if head.next == head:\n",
    "            head.next = node \n",
    "            node.next = head \n",
    "            return head\n",
    "        \n",
    "        cur = head\n",
    "        nxt = head.next\n",
    "\n",
    "        while head != nxt: # !!!!\n",
    "            if cur.val <= insertVal <= nxt.val:\n",
    "                break \n",
    "            if cur.val > nxt.val:   #注意这条命令\n",
    "                if insertVal > cur.val or insertVal < nxt.val:\n",
    "                    break \n",
    "            \n",
    "            cur = cur.next \n",
    "            nxt = nxt.next\n",
    "            \n",
    "        cur.next = node \n",
    "        node.next = nxt\n",
    "        return head\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\"\"\"\n",
    "# Definition for a Node.\n",
    "class Node:\n",
    "    def __init__(self, val=None, next=None):\n",
    "        self.val = val\n",
    "        self.next = next\n",
    "\"\"\"\n",
    "\n",
    "class Solution:\n",
    "    def insert(self, head: 'Node', insertVal: int) -> 'Node':\n",
    "        node = Node(insertVal)\n",
    "        if head is None:\n",
    "            node.next = node\n",
    "            return node\n",
    "        if head.next == head:\n",
    "            head.next = node\n",
    "            node.next = head\n",
    "            return head\n",
    "\n",
    "        curr = head\n",
    "        next = head.next\n",
    "\n",
    "        while next != head:\n",
    "            if curr.val <= insertVal <= next.val:\n",
    "                break\n",
    "            if curr.val > next.val:\n",
    "                if insertVal > curr.val or insertVal < next.val:\n",
    "                    break\n",
    "            curr = curr.next\n",
    "            next = next.next\n",
    "        curr.next = node\n",
    "        node.next = next\n",
    "        return head"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\"\"\"\n",
    "# Definition for a Node.\n",
    "class Node:\n",
    "    def __init__(self, val=None, next=None):\n",
    "        self.val = val\n",
    "        self.next = next\n",
    "\"\"\"\n",
    "\n",
    "class Solution:\n",
    "    def insert(self, head: 'Node', insertVal: int) -> 'Node':\n",
    "        if head == None :\n",
    "             head = Node(val=insertVal)\n",
    "             head.next = head \n",
    "             return head\n",
    "        p = head\n",
    "        while p.next !=head:\n",
    "            if insertVal >= p.val and  insertVal <= p.next.val:\n",
    "                break\n",
    "            if insertVal <=p.val and  p.val<=insertVal<=p.next.val:\n",
    "                break\n",
    "            if p.val > p.next.val and p.val <= insertVal:\n",
    "                break\n",
    "            if p.val>p.next.val and p.next.val >=insertVal:\n",
    "                break\n",
    "            p = p.next\n",
    "\n",
    "         \n",
    "        a = Node(insertVal)\n",
    "        a.next = p.next\n",
    "        p.next = a\n",
    "        return head"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\"\"\"\n",
    "# Definition for a Node.\n",
    "class Node:\n",
    "    def __init__(self, val=None, next=None):\n",
    "        self.val = val\n",
    "        self.next = next\n",
    "\"\"\"\n",
    "\n",
    "class Solution:\n",
    "    def insert(self, head: 'Node', insertVal: int) -> 'Node':\n",
    "        inst = Node(insertVal)\n",
    "        if not head:\n",
    "            inst.next = inst\n",
    "            return inst\n",
    "        node = head\n",
    "        while node.next != head:\n",
    "            if node.val <= insertVal <= node.next.val:\n",
    "                break\n",
    "            if node.val > node.next.val and (insertVal >= node.val or insertVal <= node.next.val):\n",
    "                break\n",
    "            node = node.next\n",
    "        inst.next = node.next\n",
    "        node.next = inst\n",
    "        return head"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\"\"\"\n",
    "# Definition for a Node.\n",
    "class Node:\n",
    "    def __init__(self, val=None, next=None):\n",
    "        self.val = val\n",
    "        self.next = next\n",
    "\"\"\"\n",
    "\n",
    "class Solution:\n",
    "    def insert(self, head: 'Node', insertVal: int) -> 'Node':\n",
    "        node = Node(insertVal)\n",
    "        if head is None:\n",
    "            node.next = node\n",
    "            return node\n",
    "        \n",
    "        if head.next == head:\n",
    "            head.next = node\n",
    "            node.next = head\n",
    "            return head\n",
    "        \n",
    "        cur = head.next\n",
    "        minval = head.val\n",
    "        maxval = head.val\n",
    "        while cur != head:\n",
    "            minval = min(minval, cur.val)\n",
    "            maxval = max(maxval, cur.val)\n",
    "            cur = cur.next\n",
    "        \n",
    "        if insertVal <= minval or insertVal >= maxval:\n",
    "            cur = head\n",
    "            while not (cur.val == maxval and cur.next.val == minval):\n",
    "                cur = cur.next\n",
    "            node.next = cur.next\n",
    "            cur.next = node\n",
    "        else:\n",
    "            cur = head\n",
    "            while not (cur.val <= insertVal and cur.next.val >= insertVal):\n",
    "                cur = cur.next\n",
    "            node.next = cur.next\n",
    "            cur.next = node\n",
    "\n",
    "        return head\n",
    "\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\"\"\"\n",
    "# Definition for a Node.\n",
    "class Node:\n",
    "    def __init__(self, val=None, next=None):\n",
    "        self.val = val\n",
    "        self.next = next\n",
    "\"\"\"\n",
    "\n",
    "class Solution:\n",
    "    def insert(self, head: 'Node', insertVal: int) -> 'Node':\n",
    "        temp=Node(insertVal)\n",
    "        cur=head\n",
    "        if not head:\n",
    "            temp.next=temp\n",
    "            return temp\n",
    "        if head.next==head:\n",
    "            head.next=temp\n",
    "            temp.next=head\n",
    "            return head\n",
    "\n",
    "        while head:\n",
    "            if temp.val>=head.val and temp.val<=head.next.val:\n",
    "                temp.next=head.next\n",
    "                head.next=temp\n",
    "                return cur\n",
    "\n",
    "            if head.val>head.next.val and ((temp.val>=head.val and temp.val>head.next.val) or(temp.val<=head.val and temp.val<head.next.val)):\n",
    "                temp.next=head.next\n",
    "                head.next=temp\n",
    "                return cur\n",
    "\n",
    "            if head.next==cur:\n",
    "                break\n",
    "            head=head.next\n",
    "\n",
    "        temp.next=head.next\n",
    "        head.next=temp\n",
    "\n",
    "        return cur"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from typing import Optional\n",
    "\n",
    "\n",
    "class Node:\n",
    "    def __init__(self, val: int = None, next: \"Node\" = None) -> None:\n",
    "        self.val = val\n",
    "        self.next = next\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def insert(self, head: Optional[Node], insertVal: int) -> Node:\n",
    "        new_node = Node(insertVal)\n",
    "        if head is None:\n",
    "            new_node.next = new_node\n",
    "            return new_node\n",
    "        if head.next == head:\n",
    "            head.next = new_node\n",
    "            new_node.next = head\n",
    "            return head\n",
    "        curr, next = head, head.next\n",
    "        while True:\n",
    "            c_v, n_v, i_v = curr.val, next.val, insertVal\n",
    "            if (c_v <= n_v and i_v >= c_v and i_v <= n_v) or (\n",
    "                c_v > n_v and (i_v >= c_v or i_v <= n_v)\n",
    "            ):\n",
    "                curr.next = new_node\n",
    "                new_node.next = next\n",
    "                return head\n",
    "            curr, next = curr.next, next.next\n",
    "            if curr == head:\n",
    "                break\n",
    "        # All values are the same\n",
    "        curr.next = new_node\n",
    "        new_node.next = next\n",
    "        return head\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def insert(self, head: 'Node', val: int) -> 'Node':\n",
    "        if head is None: # 情况一: 链表为空\n",
    "            newNode = Node(val)\n",
    "            newNode.next = newNode\n",
    "            return newNode\n",
    "        # 情况二：链表只有一个节点: 此情况其实是情况五的特例，因此代码可以省略。\n",
    "\n",
    "        ptr = head\n",
    "        while ptr.next != head: # 情况五：死循环\n",
    "            if ptr.val <= val <= ptr.next.val: # 情况三：普通情况\n",
    "                break\n",
    "            if ptr.val > ptr.next.val and (val <= ptr.next.val or val >= ptr.val): #情况四：首尾相接\n",
    "                break\n",
    "            ptr = ptr.next\n",
    "        ptr.next = Node(val,ptr.next)\n",
    "        return head\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\"\"\"\n",
    "# Definition for a Node.\n",
    "class Node:\n",
    "    def __init__(self, val=None, next=None):\n",
    "        self.val = val\n",
    "        self.next = next\n",
    "\"\"\"\n",
    "\n",
    "class Solution:\n",
    "    def insert(self, head: 'Node', insertVal: int) -> 'Node':\n",
    "        if head is None:\n",
    "            new_node = Node(val=insertVal)\n",
    "            new_node.next = new_node\n",
    "            return new_node\n",
    "        \n",
    "        if head.next is None:\n",
    "            new_node = Node(val=insertVal)\n",
    "            new_node.next = head\n",
    "            head.next = new_node            \n",
    "            return head\n",
    "\n",
    "        node = head\n",
    "        while True:\n",
    "            if node.val <= insertVal <= node.next.val or (node.val > node.next.val and insertVal > node.val) or (node.val > node.next.val and insertVal < node.next.val):\n",
    "                new_node = Node(val=insertVal)\n",
    "                new_node.next = node.next\n",
    "                node.next = new_node\n",
    "                return head\n",
    "            node = node.next\n",
    "            if node == head:\n",
    "                break\n",
    "        \n",
    "        new_node = Node(val=insertVal)\n",
    "        new_node.next = head.next\n",
    "        head.next = new_node\n",
    "\n",
    "\n",
    "        return head"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\"\"\"\n",
    "# Definition for a Node.\n",
    "class Node:\n",
    "    def __init__(self, val=None, next=None):\n",
    "        self.val = val\n",
    "        self.next = next\n",
    "\"\"\"\n",
    "\n",
    "class Solution:\n",
    "    def insert(self, head: 'Node', insertVal: int) -> 'Node':\n",
    "        if not head:\n",
    "            head = Node(insertVal)\n",
    "            head.next = head\n",
    "            return head\n",
    "        cur = head\n",
    "        while cur.next != head:\n",
    "            if cur.val <= insertVal <= cur.next.val:\n",
    "                break\n",
    "            if cur.val > cur.next.val and (insertVal > cur.val or insertVal < cur.next.val):\n",
    "                break\n",
    "            cur = cur.next\n",
    "        cur.next = Node(insertVal, cur.next)\n",
    "        return head\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\"\"\"\n",
    "# Definition for a Node.\n",
    "class Node:\n",
    "    def __init__(self, val=None, next=None):\n",
    "        self.val = val\n",
    "        self.next = next\n",
    "\"\"\"\n",
    "\n",
    "class Solution:\n",
    "    def insert(self, head: 'Node', insertVal: int) -> 'Node':\n",
    "        inst = Node(insertVal)\n",
    "        if not head:\n",
    "            inst.next = inst\n",
    "            return inst\n",
    "        \n",
    "        node = head\n",
    "        while node.next != head:\n",
    "            if node.next.val >= insertVal >= node.val:\n",
    "                break\n",
    "\n",
    "            if node.next.val < node.val and (node.val <= insertVal or insertVal <= node.next.val):\n",
    "                break\n",
    "            node = node.next\n",
    "        inst.next = node.next\n",
    "        node.next = inst\n",
    "        return head\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\"\"\"\n",
    "# Definition for a Node.\n",
    "class Node:\n",
    "    def __init__(self, val=None, next=None):\n",
    "        self.val = val\n",
    "        self.next = next\n",
    "\"\"\"\n",
    "\n",
    "class Solution:\n",
    "    def insert(self, head: 'Node', insertVal: int) -> 'Node':\n",
    "        if not head:\n",
    "            head = Node(val=insertVal)\n",
    "            head.next = head\n",
    "            return head\n",
    "        \n",
    "        curr = head\n",
    "        while True:\n",
    "            if curr.next.val < curr.val:\n",
    "                if insertVal >= curr.val or insertVal <= curr.next.val:\n",
    "                    break\n",
    "            elif curr.val <= insertVal <= curr.next.val:\n",
    "                break\n",
    "            \n",
    "            curr = curr.next\n",
    "            if curr == head:\n",
    "                break\n",
    "            \n",
    "        newNode = Node(val=insertVal)\n",
    "        newNode.next = curr.next\n",
    "        curr.next = newNode\n",
    "        return head"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\"\"\"\n",
    "# Definition for a Node.\n",
    "class Node:\n",
    "    def __init__(self, val=None, next=None):\n",
    "        self.val = val\n",
    "        self.next = next\n",
    "\"\"\"\n",
    "\n",
    "class Solution:\n",
    "    def insert(self, head: 'Node', insertVal: int) -> 'Node':\n",
    "        if not head:\n",
    "            newNode = Node(insertVal)\n",
    "            newNode.next = newNode\n",
    "            return newNode\n",
    "        import bisect\n",
    "        vals = []\n",
    "        nodes = {}\n",
    "        vis = []\n",
    "        cur = head\n",
    "        while True:\n",
    "            #print(vals,[x.val for x in vis])\n",
    "            if cur in vis:\n",
    "                break\n",
    "            if cur.val == cur.next.val:\n",
    "                vis.append(cur)\n",
    "                cur = cur.next\n",
    "                continue\n",
    "            bisect.insort(vals,cur.val)\n",
    "            nodes[cur.val] = cur\n",
    "            vis.append(cur)\n",
    "            cur = cur.next\n",
    "        if not vals:\n",
    "            nodes[cur.val] = cur\n",
    "            vals = [cur.val]\n",
    "        pos = bisect.bisect_left(vals,insertVal)\n",
    "        pos -= 1\n",
    "        newNode = Node(insertVal)\n",
    "        print(pos,vals)\n",
    "        nnxt = nodes[vals[pos]].next\n",
    "        nodes[vals[pos]].next = newNode\n",
    "        newNode.next = nnxt\n",
    "        return head"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\"\"\"\n",
    "# Definition for a Node.\n",
    "class Node:\n",
    "    def __init__(self, val=None, next=None):\n",
    "        self.val = val\n",
    "        self.next = next\n",
    "\"\"\"\n",
    "\n",
    "class Solution:\n",
    "    def insert(self, head: 'Node', insertVal: int) -> 'Node':\n",
    "        if not head:\n",
    "            t = Node(insertVal)\n",
    "            t.next = t\n",
    "            return t\n",
    "        if head.next == head:\n",
    "            head.next = Node(insertVal)\n",
    "            head.next.next = head\n",
    "            return head\n",
    "        flag = False\n",
    "        res = head\n",
    "        max_node = None\n",
    "        max_val = float('-inf')\n",
    "        head_cnt = 0\n",
    "        while not flag:\n",
    "\n",
    "            if head_cnt > 1:\n",
    "                break\n",
    "            if head == res:\n",
    "                head_cnt += 1\n",
    "            if head.val <= insertVal < head.next.val:\n",
    "                t = head.next\n",
    "                head.next = Node(insertVal)\n",
    "                head.next.next = t\n",
    "                flag = True\n",
    "            if head.val >= max_val:\n",
    "                max_val = head.val\n",
    "                max_node = head\n",
    "            head = head.next\n",
    "            \n",
    "        if not flag:\n",
    "            t = max_node.next\n",
    "            max_node.next = Node(insertVal)\n",
    "            max_node.next.next = t\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\"\"\"\n",
    "# Definition for a Node.\n",
    "class Node:\n",
    "    def __init__(self, val=None, next=None):\n",
    "        self.val = val\n",
    "        self.next = next\n",
    "\"\"\"\n",
    "\n",
    "class Solution:\n",
    "    def insert(self, head: 'Node', insertVal: int) -> 'Node':\n",
    "        if not head:\n",
    "            head = Node(insertVal)\n",
    "            head.next = head\n",
    "            return head\n",
    "        elif head.next == head:\n",
    "            p = Node(insertVal)\n",
    "            p.next = head\n",
    "            head.next = p\n",
    "            return head\n",
    "        q = head\n",
    "        while True:\n",
    "            if head.val <= head.next.val:\n",
    "                if head.val <= insertVal <= head.next.val:\n",
    "                    p = Node(insertVal)\n",
    "                    p.next = head.next\n",
    "                    head.next = p\n",
    "                    return q\n",
    "            elif head.val > head.next.val:\n",
    "                if head.val <= insertVal or insertVal <= head.next.val:\n",
    "                    p = Node(insertVal)\n",
    "                    p.next = head.next\n",
    "                    head.next = p\n",
    "                    return q\n",
    "            head = head.next\n",
    "            if q == head:\n",
    "                p = Node(insertVal)\n",
    "                p.next = head.next\n",
    "                head.next = p\n",
    "                return q\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\"\"\"\n",
    "# Definition for a Node.\n",
    "class Node:\n",
    "    def __init__(self, val=None, next=None):\n",
    "        self.val = val\n",
    "        self.next = next\n",
    "\"\"\"\n",
    "\n",
    "class Solution:\n",
    "    def insert(self, head: 'Node', insertVal: int) -> 'Node':\n",
    "        insert = ListNode(insertVal)\n",
    "        if not head: \n",
    "            insert.next = insert \n",
    "            return insert\n",
    "        if not head.next:\n",
    "            head.next = insert\n",
    "            insert.next = head\n",
    "            return head\n",
    "        cur = head\n",
    "        nxt= cur.next\n",
    "        while nxt != head:\n",
    "            if cur.val <= insertVal <= nxt.val:\n",
    "                break\n",
    "            if cur.val > nxt.val:\n",
    "                if insertVal > cur.val or insertVal < nxt.val:\n",
    "                    break     \n",
    "            cur = cur.next\n",
    "            nxt = nxt.next\n",
    "        cur.next = insert\n",
    "        insert.next = nxt\n",
    "        return head\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "        \n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\"\"\"\n",
    "# Definition for a Node.\n",
    "class Node:\n",
    "    def __init__(self, val=None, next=None):\n",
    "        self.val = val\n",
    "        self.next = next\n",
    "\"\"\"\n",
    "\n",
    "class Solution:\n",
    "    def insert(self, head: 'Node', insertVal: int) -> 'Node':\n",
    "        node = Node(insertVal)\n",
    "        if head is None:\n",
    "            node.next = node\n",
    "            head = node\n",
    "            return head\n",
    "\n",
    "        if head.next == head:\n",
    "            head.next = node\n",
    "            node.next = head\n",
    "            return head\n",
    "\n",
    "        p = head.next\n",
    "        while p != head:\n",
    "            #print(p.val)\n",
    "            if p.val <= p.next.val:\n",
    "                if p.val <= insertVal and insertVal <= p.next.val:\n",
    "                    node.next = p.next\n",
    "                    p.next = node\n",
    "                    return head\n",
    "                p = p.next\n",
    "            else:\n",
    "                if (p.val <= insertVal and insertVal >= p.next.val) or \\\n",
    "                   (p.val >= insertVal and insertVal <= p.next.val) :\n",
    "                    node.next = p.next\n",
    "                    p.next = node\n",
    "                    return head\n",
    "                p = p.next\n",
    "        node.next = p.next\n",
    "        p.next = node\n",
    "        return head\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\"\"\"\n",
    "# Definition for a Node.\n",
    "class Node:\n",
    "    def __init__(self, val=None, next=None):\n",
    "        self.val = val\n",
    "        self.next = next\n",
    "\"\"\"\n",
    "\n",
    "class Solution:\n",
    "    def insert(self, head: 'Node', insertVal: int) -> 'Node':\n",
    "        node = Node(insertVal)\n",
    "        if head is None:\n",
    "            node.next = node\n",
    "            return node\n",
    "        p=head\n",
    "        while True:\n",
    "            if p.val<=insertVal and insertVal<=p.next.val or p.val>p.next.val and (insertVal<=p.next.val or insertVal>=p.val) or p.next == head:\n",
    "                node.next = p.next\n",
    "                p.next = node\n",
    "                break\n",
    "            p=p.next\n",
    "        return head\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\"\"\"\n",
    "# Definition for a Node.\n",
    "class Node:\n",
    "    def __init__(self, val=None, next=None):\n",
    "        self.val = val\n",
    "        self.next = next\n",
    "\"\"\"\n",
    "\n",
    "class Solution:\n",
    "    def insert(self, head: 'Node', insertVal: int) -> 'Node':\n",
    "      if not head:\n",
    "        head = Node(insertVal)\n",
    "        head.next = head\n",
    "        return head\n",
    "\n",
    "      prev, pos = None, head\n",
    "      nodes_set = set()\n",
    "      flag = False\n",
    "      max_node, min_node, max_prev, min_prev = head, head, None, None\n",
    "      while True:\n",
    "        if max_node.val <= pos.val:\n",
    "          max_node = pos\n",
    "          max_prev = prev\n",
    "          min_node = pos.next\n",
    "          min_prev = pos\n",
    "\n",
    "        if prev and (prev.val <= insertVal and pos.val >= insertVal):\n",
    "          prev.next = Node(insertVal, pos)\n",
    "          flag = True\n",
    "          break\n",
    "\n",
    "        if pos in nodes_set:\n",
    "          break\n",
    "        nodes_set.add(pos)\n",
    "        prev, pos = pos, pos.next\n",
    "\n",
    "      if not flag:\n",
    "        if max_node.val == min_node.val:\n",
    "          head.next = Node(insertVal, head.next)\n",
    "        elif insertVal < min_node.val:\n",
    "          max_node.next = Node(insertVal, min_node)\n",
    "        elif insertVal > max_node.val:\n",
    "          max_node.next = Node(insertVal, max_node.next)\n",
    "\n",
    "      return head"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\"\"\"\n",
    "# Definition for a Node.\n",
    "class Node:\n",
    "    def __init__(self, val=None, next=None):\n",
    "        self.val = val\n",
    "        self.next = next\n",
    "\"\"\"\n",
    "\n",
    "class Solution:\n",
    "    def insert(self, head: 'Node', val: int) -> 'Node':\n",
    "        if not head:\n",
    "            ans = ListNode(val)\n",
    "            ans.next = ans\n",
    "            return ans\n",
    "        if head.next == head:\n",
    "            head.next = ListNode(val)\n",
    "            head.next.next = head\n",
    "            return head\n",
    "        x = head\n",
    "        while x.next != head:\n",
    "            if x.val <= val <= x.next.val or val < x.next.val < x.val or x.next.val < x.val < val:\n",
    "                t = ListNode(val, x.next)\n",
    "                x.next = t\n",
    "                return head\n",
    "            x = x.next\n",
    "        tail = x\n",
    "        tail.next = ListNode(val, head)\n",
    "        return head\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\"\"\"\n",
    "# Definition for a Node.\n",
    "class Node:\n",
    "    def __init__(self, val=None, next=None):\n",
    "        self.val = val\n",
    "        self.next = next\n",
    "\"\"\"\n",
    "\n",
    "# class Solution:\n",
    "#     def insert(self, head: 'Node', insertVal: int) -> 'Node':\n",
    "\n",
    "\n",
    "class Solution:\n",
    "\tdef find_head(self, head: 'Node'):\n",
    "\t\thead_real = None\n",
    "\t\tnext_node = head.next\n",
    "\t\tbefore_node = head\n",
    "\t\tflag = 1\n",
    "\t\twhile next_node.val >= before_node.val and flag != 2:\n",
    "\t\t\tbefore_node = next_node\n",
    "\t\t\tnext_node = next_node.next\n",
    "\t\t\tif before_node == head:\n",
    "\t\t\t\tflag += 1\n",
    "\t\treturn next_node\n",
    "\t\n",
    "\tdef insert(self, head: 'Node', insertVal: int) -> 'Node':\n",
    "\t\t#  1 2 3 4 find the first positon, before, now, next, before.val <= now.val <= next.val\n",
    "\t\t# 1  so, now != head\n",
    "\t\t#  before.val <= now.val <= next.val and now != head:\n",
    "\t\tif head is None:\n",
    "\t\t\thead = Node(insertVal)\n",
    "\t\t\thead.next = head\n",
    "\t\t\treturn head\n",
    "\t\thead_real = self.find_head(head)\n",
    "\t\tbefore_node = head_real\n",
    "\t\tnext_node = before_node.next\n",
    "\t\tif insertVal < before_node.val:\n",
    "\t\t\ttemp = before_node\n",
    "\t\t\twhile temp.next != before_node:\n",
    "\t\t\t\ttemp = temp.next\n",
    "\t\t\tinsert_node = Node(insertVal, None)\n",
    "\t\t\tinsert_node.next = before_node\n",
    "\t\t\ttemp.next = insert_node\n",
    "\t\telse:\n",
    "\t\t\twhile (\n",
    "\t\t\t\tinsertVal < before_node.val or insertVal > next_node.val or before_node.val > next_node.val) and next_node != head_real:\n",
    "\t\t\t\tprint(before_node.val, next_node.val)\n",
    "\t\t\t\tbefore_node = next_node\n",
    "\t\t\t\tnext_node = next_node.next\n",
    "\t\t\ttemp = Node(insertVal, None)\n",
    "\t\t\tbefore_node.next = temp\n",
    "\t\t\ttemp.next = next_node\n",
    "\t\treturn head"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def insert(self, head: 'Node', insertVal: int) -> 'Node':\n",
    "        node = Node(insertVal)\n",
    "        if head is None:\n",
    "            node.next = node\n",
    "            return node\n",
    "        if head.next == head:\n",
    "            head.next = node\n",
    "            node.next = head\n",
    "            return head\n",
    "        curr = head\n",
    "        next = head.next\n",
    "        while next != head:\n",
    "            if curr.val <= insertVal <= next.val:\n",
    "                break\n",
    "            if curr.val > next.val:\n",
    "                if insertVal > curr.val or insertVal < next.val:\n",
    "                    break\n",
    "            curr = curr.next\n",
    "            next = next.next\n",
    "        curr.next = node\n",
    "        node.next = next\n",
    "        return head\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\"\"\"\n",
    "# Definition for a Node.\n",
    "class Node:\n",
    "    def __init__(self, val=None, next=None):\n",
    "        self.val = val\n",
    "        self.next = next\n",
    "\"\"\"\n",
    "\n",
    "class Solution:\n",
    "    def insert(self, head: 'Node', insertVal: int) -> 'Node':\n",
    "        new = Node(insertVal)\n",
    "\n",
    "        if not head:\n",
    "            new.next = new\n",
    "            return new\n",
    "        if not head.next:\n",
    "            new.next = head\n",
    "            head.next = new\n",
    "            return head\n",
    "\n",
    "        p, max_p = head, head\n",
    "        while True:\n",
    "            if p.val >= max_p.val:\n",
    "                max_p = p\n",
    "\n",
    "            if p.val <= insertVal <= p.next.val:\n",
    "                break\n",
    "\n",
    "            p = p.next\n",
    "            if p == head:\n",
    "                break\n",
    "            \n",
    "        if p != head:\n",
    "            tmp = p.next\n",
    "            p.next = new\n",
    "            new.next = tmp\n",
    "        else:\n",
    "            tmp = max_p.next\n",
    "            max_p.next = new\n",
    "            new.next = tmp\n",
    "        return head"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\"\"\"\n",
    "# Definition for a Node.\n",
    "class Node:\n",
    "    def __init__(self, val=None, next=None):\n",
    "        self.val = val\n",
    "        self.next = next\n",
    "\"\"\"\n",
    "\n",
    "class Solution:\n",
    "    def insert(self, head: 'Node', insertVal: int) -> 'Node':\n",
    "        newNode = Node(insertVal)\n",
    "        if head is None:\n",
    "            newNode.next = newNode\n",
    "            return newNode\n",
    "        cur, nxt = head, head.next\n",
    "        if cur == nxt:\n",
    "            cur.next = newNode\n",
    "            newNode.next = nxt\n",
    "            return head\n",
    "        while nxt != head:\n",
    "            if cur.val <= insertVal <= nxt.val:\n",
    "                break\n",
    "            if cur.val > nxt.val:\n",
    "                if insertVal > cur.val or insertVal < nxt.val:\n",
    "                    break\n",
    "            cur, nxt = nxt, nxt.next\n",
    "        cur.next = newNode\n",
    "        newNode.next = nxt\n",
    "        return head\n",
    "        \n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\"\"\"\n",
    "# Definition for a Node.\n",
    "class Node:\n",
    "    def __init__(self, val=None, next=None):\n",
    "        self.val = val\n",
    "        self.next = next\n",
    "\"\"\"\n",
    "\n",
    "class Solution:\n",
    "    def insert(self, head: 'Node', insertVal: int) -> 'Node':\n",
    "        if head is None:\n",
    "            head = Node(insertVal, None)\n",
    "            head.next = head\n",
    "            return head\n",
    "        flag = True\n",
    "\n",
    "        p = head\n",
    "        while p.next != head:\n",
    "            if (insertVal >= p.val and insertVal <= p.next.val) or (p.next.val < p.val and (insertVal < p.next.val or insertVal > p.val)):\n",
    "                t = Node(insertVal, p.next)\n",
    "                p.next = t\n",
    "                flag = False\n",
    "                break\n",
    "            p = p.next\n",
    "\n",
    "        if flag:\n",
    "            t = Node(insertVal, p.next)\n",
    "            p.next = t\n",
    "        return head\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\"\"\"\n",
    "# Definition for a Node.\n",
    "class Node:\n",
    "    def __init__(self, val=None, next=None):\n",
    "        self.val = val\n",
    "        self.next = next\n",
    "\"\"\"\n",
    "\n",
    "class Solution:\n",
    "    def insert(self, head: 'Node', insertVal: int) -> 'Node':\n",
    "        node = Node(insertVal)\n",
    "        if not head:\n",
    "            head = node\n",
    "            head.next = head\n",
    "            return head\n",
    "        \n",
    "        if head.next == head:\n",
    "            head.next = node\n",
    "            node.next = head\n",
    "            return head\n",
    "        \n",
    "        cur = head\n",
    "        nxt = cur.next\n",
    "        while nxt != head:\n",
    "            if cur.val <= insertVal <= nxt.val:\n",
    "                break\n",
    "            if cur.val > nxt.val:\n",
    "                if insertVal >= cur.val or insertVal <= nxt.val:\n",
    "                    break\n",
    "            cur = nxt\n",
    "            nxt = nxt.next\n",
    "        \n",
    "        cur.next = node\n",
    "        node.next = nxt\n",
    "        return head\n",
    "\n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\"\"\"\n",
    "# Definition for a Node.\n",
    "class Node:\n",
    "    def __init__(self, val=None, next=None):\n",
    "        self.val = val\n",
    "        self.next = next\n",
    "\"\"\"\n",
    "\n",
    "class Solution:\n",
    "    def insert(self, head: 'Node', insertVal: int) -> 'Node':\n",
    "        inst = Node(insertVal)\n",
    "        if not head:\n",
    "            inst.next = inst\n",
    "            return inst\n",
    "        node = head\n",
    "        while node.next != head:\n",
    "            if node.next.val >= insertVal >= node.val:\n",
    "                break\n",
    "            if node.next.val < node.val and (node.val <= insertVal or insertVal <= node.next.val):\n",
    "                break\n",
    "            node = node.next\n",
    "        inst.next = node.next\n",
    "        node.next = inst\n",
    "        return head"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def insert(self, head: 'Node', insertVal: int) -> 'Node':\n",
    "        if not head:\n",
    "            node = Node(insertVal)\n",
    "            node.next = node\n",
    "            return node\n",
    "        if head.next == head:\n",
    "            node = Node(insertVal)\n",
    "            head.next = node\n",
    "            node.next = head\n",
    "            return head\n",
    "\n",
    "        cur = head\n",
    "        max_node = head\n",
    "        while True:\n",
    "            nxt = cur.next\n",
    "            if cur.val <= insertVal <= nxt.val:\n",
    "                node = Node(insertVal)\n",
    "                cur.next = node\n",
    "                node.next = nxt\n",
    "                return head\n",
    "            if cur.val >= max_node.val:\n",
    "                max_node = cur\n",
    "            cur = cur.next\n",
    "            if cur == head:\n",
    "                break\n",
    "\n",
    "        node = Node(insertVal)\n",
    "        node.next = max_node.next\n",
    "        max_node.next = node\n",
    "\n",
    "        return head\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\"\"\"\n",
    "# Definition for a Node.\n",
    "class Node:\n",
    "    def __init__(self, val=None, next=None):\n",
    "        self.val = val\n",
    "        self.next = next\n",
    "\"\"\"\n",
    "\n",
    "class Solution:\n",
    "    def insert(self, head: 'Node', insertVal: int) -> 'Node':\n",
    "        node = Node(insertVal)\n",
    "        if not head:\n",
    "            node.next = node \n",
    "            return node \n",
    "        if head.next == head:\n",
    "            head.next = node \n",
    "            node.next = head \n",
    "            return head\n",
    "        \n",
    "        cur = head\n",
    "        nxt = head.next\n",
    "\n",
    "        while head != nxt: # !!!!\n",
    "            if cur.val <= insertVal <= nxt.val:\n",
    "                break \n",
    "            if cur.val > nxt.val:   #注意这条命令\n",
    "                if insertVal > cur.val or insertVal < nxt.val:\n",
    "                    break \n",
    "            \n",
    "            cur = cur.next \n",
    "            nxt = nxt.next\n",
    "            \n",
    "        cur.next = node \n",
    "        node.next = nxt\n",
    "        return head\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\"\"\"\n",
    "# Definition for a Node.\n",
    "class Node:\n",
    "    def __init__(self, val=None, next=None):\n",
    "        self.val = val\n",
    "        self.next = next\n",
    "\"\"\"\n",
    "\n",
    "# class Solution:\n",
    "#     def insert(self, head: 'Node', insertVal: int) -> 'Node':\n",
    "\n",
    "\n",
    "class Solution:\n",
    "\tdef find_head(self, head: 'Node'):\n",
    "\t\tnext_node = head.next\n",
    "\t\tbefore_node = head\n",
    "\t\tflag = 1\n",
    "\t\twhile next_node.val >= before_node.val and flag != 2:\n",
    "\t\t\tbefore_node = next_node\n",
    "\t\t\tnext_node = next_node.next\n",
    "\t\t\tif before_node == head:\n",
    "\t\t\t\tflag += 1\n",
    "\t\treturn next_node\n",
    "\t\n",
    "\tdef insert(self, head: 'Node', insertVal: int) -> 'Node':\n",
    "\t\tif head is None:\n",
    "\t\t\thead = Node(insertVal)\n",
    "\t\t\thead.next = head\n",
    "\t\t\treturn head\n",
    "\t\thead_real = self.find_head(head)\n",
    "\t\tbefore_node = head_real\n",
    "\t\tinsert_node = Node(insertVal, None)\n",
    "\t\tif insertVal < before_node.val:\n",
    "\t\t\tlast = before_node\n",
    "\t\t\twhile last.next != before_node:\n",
    "\t\t\t\tlast = last.next\n",
    "\t\t\tinsert_node.next = before_node\n",
    "\t\t\tlast.next = insert_node\n",
    "\t\telse:\n",
    "\t\t\tnext_node = before_node.next\n",
    "\t\t\twhile not (before_node.val <= insertVal <= next_node.val) and next_node != head_real:\n",
    "\t\t\t\tbefore_node = next_node\n",
    "\t\t\t\tnext_node = next_node.next\n",
    "\t\t\tbefore_node.next = insert_node\n",
    "\t\t\tinsert_node.next = next_node\n",
    "\t\treturn head"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\"\"\"\n",
    "# Definition for a Node.\n",
    "class Node:\n",
    "    def __init__(self, val=None, next=None):\n",
    "        self.val = val\n",
    "        self.next = next\n",
    "\"\"\"\n",
    "\n",
    "class Solution:\n",
    "    def insert(self, head: 'Node', insertVal: int) -> 'Node':\n",
    "        maxnum = 5*10**4\n",
    "        if head == None:\n",
    "            head = Node(insertVal)\n",
    "            head.next = head\n",
    "            return head\n",
    "        elif head.next == head:\n",
    "            newnode = Node(insertVal)\n",
    "            head.next = newnode\n",
    "            newnode.next = head\n",
    "            return head\n",
    "        else:\n",
    "            left = Node(0)\n",
    "            right = Node(0)\n",
    "            left.next = head\n",
    "            right.next = head.next\n",
    "            cnt = 0\n",
    "            while True:\n",
    "                cnt += 1\n",
    "                if cnt > maxnum or (left.next.val <= insertVal and right.next.val >= insertVal) or (insertVal < left.next.val and insertVal<right.next.val and left.next.val > right.next.val) or (insertVal > left.next.val and insertVal > right.next.val and left.next.val > right.next.val):\n",
    "                    break\n",
    "                left.next = left.next.next\n",
    "                right.next = right.next.next\n",
    "            newnode = Node(insertVal)\n",
    "            left.next.next = newnode\n",
    "            newnode.next = right.next\n",
    "\n",
    "            return head\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\"\"\"\n",
    "# Definition for a Node.\n",
    "class Node:\n",
    "    def __init__(self, val=None, next=None):\n",
    "        self.val = val\n",
    "        self.next = next\n",
    "\"\"\"\n",
    "\n",
    "class Solution:\n",
    "    def insert(self, head: 'Node', insertVal: int) -> 'Node':\n",
    "        if head is None:\n",
    "            head = Node(insertVal,None)\n",
    "            head.next = head\n",
    "            return head\n",
    "        elif head.next == head:\n",
    "            new_node = Node(insertVal, None)\n",
    "            \n",
    "            new_node.next = head\n",
    "            head.next = new_node\n",
    "            return head\n",
    "        \n",
    "        #头部位置 4-> 1 ==> 4->0->1\n",
    "        #中部位置 3-> 7 ==> 3->5->7\n",
    "        #尾部位置 4-> 1 ==> 4->5->1\n",
    "        #特殊情况 全等\n",
    "        pre = head\n",
    "        cur = head.next\n",
    "        while True:\n",
    "            print(f'current check:{pre.val}->{cur.val}') \n",
    "            if pre.val>cur.val:\n",
    "                if pre.val<=insertVal or cur.val>=insertVal:\n",
    "                    pass\n",
    "                    print(pre.val, cur.val)\n",
    "                    new_node = Node(insertVal, None)\n",
    "                    pre.next = new_node\n",
    "                    new_node.next = cur\n",
    "                    # head = new_node\n",
    "                    break\n",
    "            else:\n",
    "                if pre.val<=insertVal and insertVal<=cur.val:\n",
    "                    #插入\n",
    "                    print(pre.val, cur.val)\n",
    "                    new_node = Node(insertVal, None)\n",
    "                    pre.next = new_node\n",
    "                    new_node.next = cur\n",
    "                    # head = new_node\n",
    "                    break\n",
    "            \n",
    "            if cur.next==head.next:\n",
    "                new_node = Node(insertVal, None)\n",
    "                pre.next = new_node\n",
    "                new_node.next = cur\n",
    "                break\n",
    "            \n",
    "            pre = cur\n",
    "            cur = cur.next\n",
    "\n",
    "            \n",
    "            \n",
    "            # if cur==head:\n",
    "            #     break\n",
    "        \n",
    "        return head\n",
    "        \n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\"\"\"\n",
    "# Definition for a Node.\n",
    "class Node:\n",
    "    def __init__(self, val=None, next=None):\n",
    "        self.val = val\n",
    "        self.next = next\n",
    "\"\"\"\n",
    "\n",
    "class Solution:\n",
    "    def insert(self, head: 'Node', insertVal: int) -> 'Node':\n",
    "        #定义双指针，后面的比前面大，满足在二者之间则插入。\n",
    "        #极端：最大值或最小值情况，当后面的小于前面的时判断一下\n",
    "\n",
    "\n",
    "        #为空\n",
    "        if head == None:\n",
    "            new_node = Node(insertVal)\n",
    "            new_node.next = new_node\n",
    "            return new_node\n",
    "        \n",
    "        #一个\n",
    "        if head.next == head:\n",
    "            new_node = Node(insertVal)\n",
    "            head.next = new_node\n",
    "            new_node.next = head\n",
    "            return head\n",
    "\n",
    "        dummy_head = Node()\n",
    "        dummy_head = head\n",
    "        pre,after = head,head.next\n",
    "        while 1:\n",
    "            #正常情况，after>pre\n",
    "            if after.val >= pre.val:\n",
    "                #二者之间则插入\n",
    "                if pre.val <= insertVal <= after.val:\n",
    "                    new_node = Node(insertVal)\n",
    "                    new_node.next = after\n",
    "                    pre.next = new_node\n",
    "                    return dummy_head\n",
    "                else:\n",
    "                    if pre.next == dummy_head:\n",
    "                        new_node = Node(insertVal)\n",
    "                        new_node.next = after\n",
    "                        pre.next = new_node\n",
    "                        return dummy_head\n",
    "                    pre,after = pre.next,after.next\n",
    "                    continue\n",
    "                \n",
    "            #到端点了,after<pre\n",
    "            else:\n",
    "                #判断插入值是否为最小值或最大值\n",
    "                #最大值或最小都是插入在二者之间\n",
    "                if insertVal >= pre.val or insertVal <= after.val:\n",
    "                    new_node = Node(insertVal)\n",
    "                    pre.next = new_node\n",
    "                    new_node.next = after\n",
    "                    return dummy_head\n",
    "\n",
    "                else:\n",
    "                    pre,after = pre.next,after.next\n",
    "                    continue\n",
    "        \n",
    "\n",
    "\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\"\"\"\n",
    "# Definition for a Node.\n",
    "class Node:\n",
    "    def __init__(self, val=None, next=None):\n",
    "        self.val = val\n",
    "        self.next = next\n",
    "\"\"\"\n",
    "\n",
    "class Solution:\n",
    "    def insert(self, head: 'Node', insertVal: int) -> 'Node':\n",
    "        node=Node(insertVal)\n",
    "        if head is None:\n",
    "            node.next=node\n",
    "            return node\n",
    "        \n",
    "        first=head\n",
    "        sec=head.next\n",
    "\n",
    "        if head.next==head:\n",
    "            head.next=node\n",
    "            node.next=head\n",
    "            return head\n",
    "        while sec!=head:\n",
    "            if sec.val>=insertVal>=first.val:\n",
    "                break\n",
    "            if first.val>sec.val:\n",
    "                if insertVal>first.val or insertVal<sec.val:\n",
    "                    break\n",
    "            first=first.next\n",
    "            sec=sec.next\n",
    "        first.next=node\n",
    "        node.next=sec\n",
    "        return head\n",
    "            \n",
    "\n",
    "            \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\"\"\"\n",
    "# Definition for a Node.\n",
    "class Node:\n",
    "    def __init__(self, val=None, next=None):\n",
    "        self.val = val\n",
    "        self.next = next\n",
    "\"\"\"\n",
    "\n",
    "class Solution:\n",
    "    def insert(self, head: 'Node', insertVal: int) -> 'Node':\n",
    "        if head is None:\n",
    "            cur = Node(insertVal)\n",
    "            cur.next = cur\n",
    "            return cur\n",
    "        cur = head\n",
    "        create = Node(insertVal)\n",
    "        while cur.next != head:\n",
    "            pre = cur\n",
    "            cur = cur.next\n",
    "            if pre.val <= insertVal and (insertVal <= cur.val or pre.val > cur.val):\n",
    "                pre.next = create\n",
    "                create.next = cur\n",
    "                return head\n",
    "            if pre.val >= insertVal and insertVal <= cur.val and pre.val > cur.val:\n",
    "                pre.next = create\n",
    "                create.next = cur\n",
    "                return head\n",
    "                \n",
    "        cur.next = create\n",
    "        create.next = head\n",
    "        return head\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\"\"\"\n",
    "# Definition for a Node.\n",
    "class Node:\n",
    "    def __init__(self, val=None, next=None):\n",
    "        self.val = val\n",
    "        self.next = next\n",
    "\"\"\"\n",
    "\n",
    "class Solution:\n",
    "    def insert(self, head: 'Node', insertVal: int) -> 'Node':\n",
    "        insert_node = Node(insertVal)\n",
    "        if not head:\n",
    "            insert_node.next = insert_node\n",
    "            return insert_node\n",
    "        node = head\n",
    "        while node.next != head:\n",
    "            if node.next.val >= insertVal >= node.val:\n",
    "                break\n",
    "            if node.next.val < node.val and (node.val <= insertVal or insertVal <= node.next.val):\n",
    "                break\n",
    "            node = node.next\n",
    "\n",
    "        insert_node.next = node.next\n",
    "        node.next = insert_node\n",
    "        return head\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\"\"\"\n",
    "# Definition for a Node.\n",
    "class Node:\n",
    "    def __init__(self, val=None, next=None):\n",
    "        self.val = val\n",
    "        self.next = next\n",
    "\"\"\"\n",
    "\n",
    "class Solution:\n",
    "    def insert(self, head: 'Node', insertVal: int) -> 'Node':\n",
    "        node = Node(insertVal)\n",
    "        if head is None:\n",
    "            node.next = node\n",
    "            return node\n",
    "        if head.next == head:\n",
    "            head.next = node\n",
    "            node.next = head\n",
    "            return head\n",
    "        curr = head\n",
    "        next = head.next\n",
    "        while next != head:\n",
    "            if curr.val <= insertVal <= next.val:\n",
    "                break\n",
    "            if curr.val > next.val:\n",
    "                if insertVal > curr.val or insertVal < next.val:\n",
    "                    break\n",
    "            curr = curr.next\n",
    "            next = next.next\n",
    "        curr.next = node\n",
    "        node.next = next\n",
    "        return head\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\"\"\"\n",
    "# Definition for a Node.\n",
    "class Node:\n",
    "    def __init__(self, val=None, next=None):\n",
    "        self.val = val\n",
    "        self.next = next\n",
    "\"\"\"\n",
    "\n",
    "class Solution:\n",
    "    def insert(self, head: 'Node', insertVal: int) -> 'Node':\n",
    "        if head == None:\n",
    "            node = Node(insertVal,None)\n",
    "            node.next = node\n",
    "            return node\n",
    "        pre = head\n",
    "        cur = head.next\n",
    "        min_node = None\n",
    "        while cur != head:\n",
    "            if cur.val < pre.val:\n",
    "                min_node = cur\n",
    "                break\n",
    "            cur = cur.next\n",
    "            pre = pre.next\n",
    "        if min_node == None:\n",
    "            min_node = head\n",
    "        pre = min_node\n",
    "        cur = min_node.next        \n",
    "        \n",
    "        while cur != min_node:\n",
    "            if (insertVal>pre.val and insertVal < cur.val) or pre.val == insertVal:\n",
    "                node = Node(insertVal,None)\n",
    "                pre.next = node\n",
    "                node.next = cur\n",
    "                break\n",
    "            cur = cur.next\n",
    "            pre = pre.next\n",
    "\n",
    "        if cur == min_node:\n",
    "            node = Node(insertVal,None)\n",
    "            pre.next = node\n",
    "            node.next = cur\n",
    "            \n",
    "        return head\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\"\"\"\n",
    "# Definition for a Node.\n",
    "class Node:\n",
    "    def __init__(self, val=None, next=None):\n",
    "        self.val = val\n",
    "        self.next = next\n",
    "\"\"\"\n",
    "\n",
    "class Solution:\n",
    "    def insert(self, head: 'Node', insertVal: int) -> 'Node':\n",
    "        x = ListNode(insertVal)\n",
    "        x.next = x # 需要循环\n",
    "        if not head:\n",
    "            return x\n",
    "        res = head\n",
    "        min_val, max_val = head.val, head.val\n",
    "        # 遍历一次返回头节点, 找序列中的最大和最小值\n",
    "        while head.next != res:\n",
    "            head = head.next\n",
    "            min_val = min(min_val, head.val)\n",
    "            max_val = max(max_val, head.val)\n",
    "        # 最大值=最小值，序列值均相同，插在任意位置\n",
    "        if min_val == max_val:\n",
    "            x.next = head.next\n",
    "            head.next = x\n",
    "        else:\n",
    "            # 找到最大值最小值转换位置\n",
    "            while not (head.val == max_val and head.next.val == min_val):\n",
    "                head = head.next\n",
    "            # 插入值在(最小值，最大值)，用head来寻找合适的区间[head, head.next]\n",
    "            while not (x.val >= max_val or x.val <= min_val) and not (head.val <= x.val <= head.next.val):\n",
    "                head = head.next\n",
    "            # 插入值>=最大值或者<=最小值\n",
    "            x.next = head.next\n",
    "            head.next = x\n",
    "        return res\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\"\"\"\n",
    "# Definition for a Node.\n",
    "class Node:\n",
    "    def __init__(self, val=None, next=None):\n",
    "        self.val = val\n",
    "        self.next = next\n",
    "\"\"\"\n",
    "\n",
    "class Solution:\n",
    "    def insert(self, head: 'Node', insertVal: int) -> 'Node':\n",
    "        node = Node(insertVal)\n",
    "        if not head:\n",
    "            head = node\n",
    "            head.next = head\n",
    "            return head\n",
    "        if not head.next:\n",
    "            head.next = node\n",
    "            head.next.next = head\n",
    "            return head\n",
    "        cur = head\n",
    "        nxt = head.next\n",
    "        while nxt != head:\n",
    "            if cur.val <= insertVal <= nxt.val:\n",
    "                break\n",
    "            if cur.val > nxt.val:\n",
    "                if insertVal >= cur.val or insertVal <= nxt.val:\n",
    "                    break\n",
    "            cur = cur.next\n",
    "            nxt = nxt.next\n",
    "        cur.next = node\n",
    "        node.next = nxt\n",
    "        return head"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a Node.\n",
    "class Node:\n",
    "    def __init__(self, val=None, next=None):\n",
    "        self.val = val\n",
    "        self.next = next\n",
    "\n",
    "class Solution:\n",
    "    def insert(self, head: 'Node', insertVal: int) -> 'Node':\n",
    "        # 如果链表为空\n",
    "        if not head:\n",
    "            newNode = Node(insertVal, None)\n",
    "            newNode.next = newNode\n",
    "            return newNode\n",
    "        \n",
    "        prev, current = head, head.next\n",
    "        toInsert = False\n",
    "        \n",
    "        while True:\n",
    "            # 情况1: 在中间插入\n",
    "            if prev.val <= insertVal <= current.val:\n",
    "                toInsert = True\n",
    "            # 情况2: 插入到链表的末尾\n",
    "            elif prev.val > current.val:\n",
    "                if insertVal >= prev.val or insertVal <= current.val:\n",
    "                    toInsert = True\n",
    "            \n",
    "            if toInsert:\n",
    "                prev.next = Node(insertVal, current)\n",
    "                return head\n",
    "            \n",
    "            prev, current = current, current.next\n",
    "            # 如果已经遍历了整个循环链表\n",
    "            if prev == head:\n",
    "                break\n",
    "        \n",
    "        # 没有合适的位置，插入到链表的末尾\n",
    "        prev.next = Node(insertVal, current)\n",
    "        return head\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\"\"\"\n",
    "# Definition for a Node.\n",
    "class Node:\n",
    "    def __init__(self, val=None, next=None):\n",
    "        self.val = val\n",
    "        self.next = next\n",
    "\"\"\"\n",
    "\n",
    "class Solution:\n",
    "    def insert(self, head: 'Node', insertVal: int) -> 'Node':\n",
    "        node = Node(insertVal)\n",
    "        if head is None:\n",
    "            node.next = node\n",
    "            return node\n",
    "        if head.next == head:\n",
    "            head.next = node\n",
    "            node.next = head\n",
    "            return head\n",
    "        \n",
    "        cur = head\n",
    "        nt = head.next\n",
    "\n",
    "        while nt != head:\n",
    "            if cur.val <= insertVal <= nt.val:\n",
    "                break\n",
    "            if cur.val > nt.val:\n",
    "                if insertVal > cur.val or insertVal < nt.val:\n",
    "                    break\n",
    "                \n",
    "            cur =cur.next\n",
    "            nt = nt.next\n",
    "        \n",
    "        cur.next = node\n",
    "        node.next = nt\n",
    "    \n",
    "        return head"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\"\"\"\n",
    "# Definition for a Node.\n",
    "class Node:\n",
    "    def __init__(self, val=None, next=None):\n",
    "        self.val = val\n",
    "        self.next = next\n",
    "\"\"\"\n",
    "\n",
    "class Solution:\n",
    "    def insert(self, head: 'Node', insertVal: int) -> 'Node':\n",
    "        node = Node(insertVal)\n",
    "        if not head:\n",
    "            node.next = node\n",
    "            return node\n",
    "        if head.next == head:\n",
    "            head.next = node\n",
    "            node.next = head\n",
    "            return head\n",
    "        p, q = head, head.next\n",
    "        while q != head:\n",
    "            if p.val <= insertVal <= q.val:\n",
    "                break\n",
    "            if p.val > q.val:\n",
    "                if insertVal > p.val or insertVal < q.val:\n",
    "                    break\n",
    "            p = p.next\n",
    "            q = q.next\n",
    "        p.next = node\n",
    "        node.next = q\n",
    "        return head\n",
    "        \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\"\"\"\n",
    "# Definition for a Node.\n",
    "class Node:\n",
    "    def __init__(self, val=None, next=None):\n",
    "        self.val = val\n",
    "        self.next = next\n",
    "\"\"\"\n",
    "\n",
    "class Solution:\n",
    "    def insert(self, head: 'Node', insertVal: int) -> 'Node':\n",
    "        def get_tail(head):\n",
    "            if not head:\n",
    "                return head\n",
    "            cursor = head\n",
    "            while cursor and cursor.next != head:\n",
    "                cursor = cursor.next\n",
    "            return cursor\n",
    "\n",
    "        if head is None:\n",
    "            head = Node(insertVal)\n",
    "            head.next = head\n",
    "            return head\n",
    "        elif head is not None and head.next == head:\n",
    "            # 只有一个节点\n",
    "            node = Node(insertVal)\n",
    "            head.next = node\n",
    "            node.next = head\n",
    "            return head\n",
    "        else:\n",
    "            # 其余情况\n",
    "            node = Node(insertVal)\n",
    "            curr = head\n",
    "            next = head.next\n",
    "            while next != head:\n",
    "                if curr.val <= insertVal <= next.val:\n",
    "                    break\n",
    "                if curr.val > next.val:\n",
    "                    if insertVal > curr.val or insertVal < next.val:\n",
    "                        break\n",
    "                curr = curr.next\n",
    "                next = next.next\n",
    "            curr.next = node\n",
    "            node.next = next\n",
    "            return head\n",
    "\n",
    "# 作者：力扣官方题解\n",
    "# 链接：https://leetcode.cn/problems/4ueAj6/solutions/1606890/pai-xu-de-xun-huan-lian-biao-by-leetcode-f566/\n",
    "# 来源：力扣（LeetCode）\n",
    "# 著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\"\"\"\n",
    "# Definition for a Node.\n",
    "class Node:\n",
    "    def __init__(self, val=None, next=None):\n",
    "        self.val = val\n",
    "        self.next = next\n",
    "\"\"\"\n",
    "\n",
    "class Solution:\n",
    "    def insert(self, head: 'Node', insertVal: int) -> 'Node':\n",
    "        t = head\n",
    "        if not head:\n",
    "            insert = ListNode(insertVal)\n",
    "            insert.next = insert\n",
    "            return insert\n",
    "\n",
    "        if head.next is head:\n",
    "            insert = ListNode(insertVal)\n",
    "            head.next = insert\n",
    "            insert.next = head\n",
    "            return head\n",
    "\n",
    "        min_v = math.pow(10, 6)\n",
    "        max_v = -math.pow(10, 6)\n",
    "        max_node = None\n",
    "        min_node = None\n",
    "        pe = head\n",
    "        if pe.val >= max_v:\n",
    "            max_v = pe.val\n",
    "            max_node = pe\n",
    "        if pe.val <= min_v:\n",
    "            min_v = pe.val\n",
    "            min_node = pe\n",
    "        ne = head.next\n",
    "        while 1:\n",
    "            # print(pe.val, insertVal, ne.val)\n",
    "            if pe.val <= insertVal <= ne.val:\n",
    "                insert = ListNode(insertVal)\n",
    "                pe.next = insert\n",
    "                insert.next = ne\n",
    "                return head\n",
    "            if ne.val >= max_v:\n",
    "                max_v = ne.val\n",
    "                max_node = ne\n",
    "            if ne.val <= min_v:\n",
    "                min_v = ne.val\n",
    "                min_node = ne\n",
    "            if ne is head:\n",
    "                break\n",
    "            pe = ne\n",
    "            ne = ne.next\n",
    "\n",
    "        if insertVal >= max_v or insertVal <= min_v:\n",
    "            insert = ListNode(insertVal)\n",
    "            if max_node is min_node:\n",
    "                t = max_node.next\n",
    "                max_node.next = insert\n",
    "                insert.next = t\n",
    "            else:\n",
    "                t = max_node.next\n",
    "                insert = ListNode(insertVal)\n",
    "                max_node.next = insert\n",
    "                insert.next = t\n",
    "\n",
    "        return head\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\"\"\"\n",
    "# Definition for a Node.\n",
    "class Node:\n",
    "    def __init__(self, val=None, next=None):\n",
    "        self.val = val\n",
    "        self.next = next\n",
    "\"\"\"\n",
    "\n",
    "class Solution:\n",
    "    def insert(self, head: 'Node', insertVal: int) -> 'Node':\n",
    "        if not head:\n",
    "            node = Node(insertVal)\n",
    "            node.next = node\n",
    "            return node\n",
    "        node=Node(insertVal)\n",
    "        now=head\n",
    "        hashset=set()\n",
    "        minnode=head\n",
    "        while now:\n",
    "            if now in hashset:\n",
    "                break\n",
    "            else:\n",
    "                hashset.add(now)\n",
    "                if now.val==insertVal:\n",
    "                    minnode=now\n",
    "                    break\n",
    "                elif now.val<insertVal:\n",
    "                    if minnode.val<insertVal:\n",
    "                        if now.val>=minnode.val:\n",
    "                            minnode=now\n",
    "                    else:\n",
    "                        minnode=now\n",
    "                    \n",
    "                else:\n",
    "                    if minnode.val>insertVal and now.val>=minnode.val:\n",
    "                        minnode=now\n",
    "            now=now.next\n",
    "        temp=minnode.next\n",
    "        minnode.next=node\n",
    "        node.next=temp\n",
    "        return head\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\"\"\"\n",
    "# Definition for a Node.\n",
    "class Node:\n",
    "    def __init__(self, val=None, next=None):\n",
    "        self.val = val\n",
    "        self.next = next\n",
    "\"\"\"\n",
    "\n",
    "class Solution:\n",
    "    def insert(self, head: 'Node', insertVal: int) -> 'Node':\n",
    "        inst = Node(insertVal)\n",
    "        if not head:\n",
    "            inst.next = inst\n",
    "            return inst\n",
    "        node = head\n",
    "        while node.next != head:\n",
    "            if node.next.val >= insertVal >= node.val:\n",
    "                break\n",
    "            if node.next.val < node.val and (node.val <= insertVal or insertVal <= node.next.val):\n",
    "                break\n",
    "            node = node.next\n",
    "        inst.next = node.next\n",
    "        node.next = inst\n",
    "        return head"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\"\"\"\n",
    "# Definition for a Node.\n",
    "class Node:\n",
    "    def __init__(self, val=None, next=None):\n",
    "        self.val = val\n",
    "        self.next = next\n",
    "\"\"\"\n",
    "\n",
    "class Solution:\n",
    "    def insert(self, head: 'Node', insertVal: int) -> 'Node':\n",
    "        if not head:\n",
    "            node = Node(insertVal)\n",
    "            node.next = node\n",
    "            return node\n",
    "        ans = head\n",
    "        while head.next != ans:\n",
    "            if head.val <= insertVal <= head.next.val:\n",
    "                break\n",
    "            if head.val > head.next.val and (insertVal > head.val or insertVal < head.next.val):\n",
    "                break\n",
    "            head = head.next\n",
    "        head.next = Node(insertVal,head.next)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\"\"\"\n",
    "# Definition for a Node.\n",
    "class Node:\n",
    "    def __init__(self, val=None, next=None):\n",
    "        self.val = val\n",
    "        self.next = next\n",
    "\"\"\"\n",
    "\n",
    "class Solution:\n",
    "    def insert(self, head: 'Node', insertVal: int) -> 'Node':\n",
    "        if not head:\n",
    "            node = Node(insertVal)\n",
    "            node.next = node \n",
    "            return node \n",
    "        pre, cur = head, head.next \n",
    "        while cur != head:\n",
    "            if pre.val <= insertVal <= cur.val:\n",
    "                break\n",
    "            elif insertVal > pre.val > cur.val or insertVal < cur.val < pre.val:\n",
    "                break\n",
    "            pre = cur \n",
    "            cur = cur.next \n",
    "        node = Node(insertVal)\n",
    "        pre.next = node \n",
    "        node.next = cur \n",
    "        return head\n",
    "          "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def insert(self, head: 'Node', insertVal: int) -> 'Node':\n",
    "        node = Node(insertVal)\n",
    "        if head is None:\n",
    "            node.next = node\n",
    "            return node\n",
    "        if head.next == head:\n",
    "            head.next = node\n",
    "            node.next = head\n",
    "            return head\n",
    "        curr = head\n",
    "        next = head.next\n",
    "        while next != head:\n",
    "            if curr.val <= insertVal <= next.val:\n",
    "                break\n",
    "            if curr.val > next.val:\n",
    "                if insertVal > curr.val or insertVal < next.val:\n",
    "                    break\n",
    "            curr = curr.next\n",
    "            next = next.next\n",
    "        curr.next = node\n",
    "        node.next = next\n",
    "        return head\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\"\"\"\n",
    "# Definition for a Node.\n",
    "class Node:\n",
    "    def __init__(self, val=None, next=None):\n",
    "        self.val = val\n",
    "        self.next = next\n",
    "\"\"\"\n",
    "\n",
    "class Solution:\n",
    "    def insert(self, head: 'Node', insertVal: int) -> 'Node':\n",
    "        newNode = Node(insertVal)\n",
    "        if head is None:\n",
    "            newNode.next = newNode\n",
    "            return newNode\n",
    "        pre = head\n",
    "        cur = pre.next\n",
    "        NodeMin, NodeMax = cur, cur\n",
    "        if pre == cur:\n",
    "            pre.next = newNode\n",
    "            newNode.next = cur\n",
    "        else:\n",
    "            if not(pre.val <= insertVal <= cur.val):\n",
    "                pre, cur = cur, cur.next\n",
    "                while not(pre.val <= insertVal <= cur.val) and cur != head.next:\n",
    "                    print(cur.val)\n",
    "                    if cur.val > NodeMax.val:\n",
    "                        NodeMax = cur\n",
    "                    if cur.val < NodeMin.val:\n",
    "                        NodeMin = cur\n",
    "                    pre, cur = cur, cur.next\n",
    "                if NodeMax.val > NodeMin.val:\n",
    "                    while NodeMax.val == NodeMax.next.val:\n",
    "                        NodeMax = NodeMax.next\n",
    "                NodeMin = NodeMax.next\n",
    "                if insertVal > NodeMax.val:\n",
    "                    NodeMax.next, newNode.next = newNode,NodeMax.next\n",
    "                elif insertVal < NodeMin.val:\n",
    "                    NodeMax.next = newNode\n",
    "                    newNode.next = NodeMin\n",
    "                else:\n",
    "                    pre.next = newNode\n",
    "                    newNode.next = cur\n",
    "            else:\n",
    "                pre.next = newNode\n",
    "                newNode.next = cur\n",
    "        return head\n",
    "        \n",
    "        "
   ]
  }
 ],
 "metadata": {},
 "nbformat": 4,
 "nbformat_minor": 2
}
